AT_arc212_b [ARC212B] Stones on Grid

There is a grid with $ N $ rows and $ N $ columns. The cell at the $ i $ -th row from the top and $ j $ -th column from the left is called cell $ (i,j) $ . You perform the following in order of $ i=1,2,\ldots,M $ : - Operation $ i $ : Choose either to place one stone on cell $ (x_i, y_i) $ or not. If you place a stone, a cost of $ c_i $ is incurred; otherwise, no cost is incurred. However, **you must place a stone in operation $ 1 $** . Determine whether the following goal can be achieved, and if it can, find the minimum sum of costs incurred. - Goal : For every $ i \ (1 \leq i \leq N) $ , the number of stones placed in the $ i $ -th row is equal to the number of stones placed in the $ i $ -th column.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ $ \vdots $ $ x_M $ $ y_M $ $ c_M $

If it is impossible to achieve the goal, output `-1`. If it is possible, output the minimum sum of costs incurred.

### Sample Explanation 1 The goal can be achieved by choosing to place a stone in operations $ 1,2,5 $ . The sum of costs in this case is $ 5+2+4=11 $ . The total cost cannot be less than $ 11 $ to achieve the goal, so the answer is $ 11 $ . ### Sample Explanation 2 You must place a stone in operation $ 1 $ . ### Constraints - $ 1 \le N, M \le 2 \times 10^5 $ - $ 1 \le x_i, y_i \le N $ - $ 1 \le c_i \le 10^9 $ - $ (x_i, y_i) $ are distinct. - All input values are integers.