{"problem":{"name":"Minimum Coloring","description":{"content":"We have a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. On this grid, there are $N$ white pieces numbered $1$ to $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc231_h"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nOn this grid, there are $N$ white pieces numbered $1$ to $N$. Piece $i$ is on $(A_i,B_i)$.\nYou can pay the cost of $C_i$ to change Piece $i$ to a black piece.\nFind the minimum total cost needed to have at least one black piece in every row and every column.\n\n## Constraints\n\n*   $1 \\leq H,W \\leq 10^3$\n*   $1 \\leq N \\leq 10^3$\n*   $1 \\leq A_i \\leq H$\n*   $1 \\leq B_i \\leq W$\n*   $1 \\leq C_i \\leq 10^9$\n*   All pairs $(A_i,B_i)$ are distinct.\n*   There is at least one white piece in every row and every column.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $N$\n$A_1$ $B_1$ $C_1$\n$\\hspace{23pt} \\vdots$\n$A_N$ $B_N$ $C_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc231_h","tags":[],"sample_group":[["2 3 6\n1 1 1\n1 2 10\n1 3 100\n2 1 1000\n2 2 10000\n2 3 100000","1110\n\nBy paying the cost of $1110$ to change Pieces $2, 3, 4$ to black pieces, we can have a black piece in every row and every column."],["1 7 7\n1 2 200000000\n1 7 700000000\n1 4 400000000\n1 3 300000000\n1 6 600000000\n1 5 500000000\n1 1 100000000","2800000000"],["3 3 8\n3 2 1\n3 1 2\n2 3 1\n2 2 100\n2 1 100\n1 3 2\n1 2 100\n1 1 100","6"]],"created_at":"2026-03-03 11:01:14"}}