{"problem":{"name":"Stones on Grid","description":{"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$:","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc212_b"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc212_b","tags":[],"sample_group":[["4 5\n2 4 5\n4 1 2\n2 1 3\n3 3 9\n1 2 4","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$."],["3 3\n1 1 1000000000\n2 2 100000000\n3 3 10000000","1000000000\n\nYou must place a stone in operation $1$."],["2 1\n1 2 10","\\-1"]],"created_at":"2026-03-03 11:01:13"}}