温迪有一个国家，他想建立一支军队来保护他的国家。他挑选了 N 个女孩和 M 个男孩，并希望收集他们成为他的士兵。要收集一个没有任何特权的士兵，他必须支付 10000 人民币。女孩和男孩之间存在一些关系，温迪可以利用这些关系来减少他的成本。如果女孩 x 和男孩 y 之间有一个关系 d，并且其中一个已经被收集，温迪可以以 10000 - d 人民币的价格收集另一个。现在给出所有女孩和男孩之间的关系，你的任务是找出温迪需要支付的最少金额。注意，每收集一个士兵只能使用一种关系。

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

每个测试用例的第一行包含三个整数 N, M, R，分别表示女孩数量、男孩数量和关系数量。

接下来 R 行，每行包含三个整数 x_i, y_i, d_i，表示女孩 x_i 和男孩 y_i 之间的关系权值。

每个测试用例之前有一个空行。

对于每个测试用例，输出一行，表示最少需要支付的金额。

• 1 \le N, M \le 10000
• 0 \le R \le 50000
• 0 \le x_i < N
• 0 \le y_i < M
• 0 < d_i < 10000