题目描述

我们有一个 $H$ 行 $W$ 列的方格。用 $(i,j)$ 表示从上到下数第 $i$ 行，从左到右数第 $j$ 列的方格。

在这个方格上，有 $N$ 个编号为 $1$ 到 $N$ 的白色棋子。棋子 $i$ 位于 $(A_i,B_i)$。

你可以花费 $C_i$ 的代价将棋子 $i$ 变为黑色棋子。

求出至少在每行和每列都有一个黑色棋子所需的最小总代价。

约束条件

• $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)$ 的组合都是不同的。
• 每一行和每一列至少有一个白色棋子。
• 输入数据中的所有值均为整数。

输入

从标准输入读入数据，输入格式如下：

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

输出

输出答案。

示例输入1

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

示例输出1

1110

通过花费 $1110$ 的代价将棋子 $2, 3, 4$ 变为黑色棋子，我们可以在每行和每列上都有一个黑色棋子。

示例输入2

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

示例输出2

2800000000

示例输入3

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

示例输出3

6