题目描述

$H$ 行 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。

グリッド上には $1$ から $N$ の番号がついた $N$ 個の白い駒が置かれています。駒 $i$ が置かれているマスは $(A_i,B_i)$ です。

あなたはコストを $C_i$ 払うことで、駒 $i$ を黒い駒に変えることができます。

どの行どの列にも黒い駒が $1$ 個以上ある状態にするために必要なコストの和の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $N$ $A_1$ $B_1$ $C_1$ $\hspace{23pt}\ \vdots$ $A_N$ $B_N$ $C_N$

输出格式

答えを出力せよ。

题目大意

芷萱姐姐有一个 $H \times W$ 的网格图，初始所有点都是白色的。

有 $N$ 个点可以被改变成黑色，这 $N$ 个点的坐标是 $a_i,b_i$，改变颜色的代价是 $c_i$。

你需要找到最小代价使得每行每列都至少有一个黑色节点。

数据保证有解。

Tanslated by Tx_Lcy

2 3 6
1 1 1
1 2 10
1 3 100
2 1 1000
2 2 10000
2 3 100000

1110

1 7 7
1 2 200000000
1 7 700000000
1 4 400000000
1 3 300000000
1 6 600000000
1 5 500000000
1 1 100000000

2800000000

3 3 8
3 2 1
3 1 2
2 3 1
2 2 100
2 1 100
1 3 2
1 2 100
1 1 100

6

提示

制約

• $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$ 個以上の白い駒が置かれている
• 入力に含まれる値は全て整数である

Sample Explanation 1

コスト $1110$ を払い駒 $2,3,4$ を黒い駒に変えることで、どの行どの列にも黒い駒がある状態にすることができます。