题目描述

光头强是森林养护员，他想建立一支巡逻队来保护他的森林。他挑选了 $N$ 只公熊和 $M$ 只母熊，想把他们征召起来组成巡逻队。正常情况下，要征召一只熊，他必须支付 $10000$ 元人民币。男女搭配干活不累，异性熊之间有一些友好关系，光头强可以利用这些关系来帮助说服对方，以降低征召成本。如果公熊 $x$ 和母熊 $y$ 有关系 $d$，并且其中一只已经被征召，光头强可让这只熊出面帮忙，以 $10000-d$ 人民币征召另一只。现在，给你公熊和母熊之间的所有关系，你的任务是找出征召这些熊所需要支付的最少金额。

请注意，在征召一只熊的时候，只能让一只与其有友好关系的熊去帮助降低成本。

输入格式

第一行输入是测试用例的数量 $T$。

每个测试用例的第一行包含三个整数，$N$、$M$ 和 $R$。

然后是 $R$ 行，每行包含三个整数 $x_i,y_i,d_i$。

输出格式

输出一个数表示答案。

2
5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781
5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133

71071
54223

测试数据规模

$1≤T≤5$

$1 ≤ N, M ≤ 10000$

$0 ≤ R ≤ 50000$

$0 ≤ x_i < N$

$0 ≤ y_i < M$

$0 < d_i < 10000$