AT_abc231_h [ABC231H] Minimum Coloring

有一个 $H$ 行 $W$ 列的网格。自上而下第 $i$ 行，自左而右第 $j$ 列的格子记作格子 $(i,j)$。 在网格上放置了 $N$ 个编号为 $1$ 到 $N$ 的白色棋子。棋子 $i$ 放在格子 $(A_i,B_i)$。 你可以支付 $C_i$ 的代价，将棋子 $i$ 变为黑色棋子。 请你求出，使得每一行和每一列至少有一个黑色棋子的状态下，所需支付的总代价的最小值。

输入以如下格式从标准输入读入。 > $H$ $W$ $N$ > $A_1$ $B_1$ $C_1$ > $\hspace{23pt}\ \vdots$ > $A_N$ $B_N$ $C_N$

请输出答案。

## 限制条件 - $1 \leq H,W \leq 10^3$ - $1 \leq N \leq 10^3$ - $1 \leq A_i \leq H$ - $1 \leq B_i \leq W$ - $1 \leq C_i \leq 10^9$ - $(A_i,B_i)$ 互不相同 - 每一行、每一列都至少有一个白色棋子 - 输入中所有值均为整数 ## 样例解释 1 支付 $1110$ 的代价，将棋子 $2,3,4$ 变为黑色棋子后，可以使得每一行和每一列都至少有一个黑色棋子。 由 ChatGPT 4.1 翻译