{"raw_statement":[{"iden":"problem statement","content":"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$:\n\n*   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.\n\nHowever, **you must place a stone in operation $1$**.\nDetermine whether the following goal can be achieved, and if it can, find the minimum sum of costs incurred.\n\n*   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."},{"iden":"constraints","content":"*   $1 \\le N, M \\le 2 \\times 10^5$\n*   $1 \\le x_i, y_i \\le N$\n*   $1 \\le c_i \\le 10^9$\n*   $(x_i, y_i)$ are distinct.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$x_1$ $y_1$ $c_1$\n$x_2$ $y_2$ $c_2$\n$\\vdots$\n$x_M$ $y_M$ $c_M$"},{"iden":"sample input 1","content":"4 5\n2 4 5\n4 1 2\n2 1 3\n3 3 9\n1 2 4"},{"iden":"sample output 1","content":"11\n\nThe goal can be achieved by choosing to place a stone in operations $1,2,5$.\nThe 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$."},{"iden":"sample input 2","content":"3 3\n1 1 1000000000\n2 2 100000000\n3 3 10000000"},{"iden":"sample output 2","content":"1000000000\n\nYou must place a stone in operation $1$."},{"iden":"sample input 3","content":"2 1\n1 2 10"},{"iden":"sample output 3","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}