Windy有一个国家，然后然后他想要建造一只军队来保护他的国家，他已经选定了N个女孩和M个男孩，然后，他想召集他们去当他的士兵。为了去收集一个没有特权的士兵，他必须支付1W人民币，男孩和女孩之间有一些关系，并且Windy可以利用这些关系去见面他的花费。如果女孩x和男孩y有关系的，并且他们中的一个已经被联系到了，Windy可以用10000-d人民币联系另外一个一个人。现在，给你所有的男孩和女孩之间的这些关系。你的任务是找出Windy需要花费最少的钱。注意：在征集一名士兵时只能使用一种关系。

输入：
输入的第一行是测试的数据组数
测试的每组数据的第一行有3个整数 N，M和R
接下来的R行，每行包括3个整数xi,yi和di
下面是每组数据的范围
1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 10000

输出:
对于每组测试数据只有一个整数即最小花费




纯手翻