{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"温迪有一个国家,他想建立一支军队来保护他的国家。他收留了N个女孩和M个男孩,想把她们收留成他的士兵。征兵无特权,必须交纳一万元。女孩和男孩之间有一些关系,温迪可以利用这些关系来降低他的成本。如果X女孩和Y男孩有D关系,并且其中一个已经被收集,Windy可以用10000-D人民币收集另一个。现在考虑到男孩和女孩之间的所有关系,你的任务是找到风必须支付的最少的钱。注意,收集一个士兵时只能使用一个关系。 "}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cdiv\u003e\n 输入的第一行是测试用例的数量。 每个测试用例的第一行包含三个整数,n、m和r。 然后R行,每个包含三个整数Xi,Yi和DI。 每个测试用例前都有一个空白行。 \n \u003cp\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eM\u003c/i\u003e ≤ 10000\u003cbr\u003e0 ≤ \u003ci\u003eR\u003c/i\u003e ≤ 50,000\u003cbr\u003e0 ≤ \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u0026lt; \u003ci\u003eN\u003c/i\u003e\u003cbr\u003e0 ≤ \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u0026lt; \u003ci\u003eM\u003c/i\u003e\u003cbr\u003e0 \u0026lt; \u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u0026lt; 10000\u003cbr\u003e\u003c/p\u003e\n \u003c/div\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n For each test case output the answer in a single line.\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\n\n5 5 8\n4 3 6831\n1 3 4583\n0 0 6592\n0 1 3063\n3 3 4975\n1 3 2049\n4 2 2104\n2 2 781\n\n5 5 10\n2 4 9820\n3 2 6236\n3 1 8864\n2 4 8326\n2 0 5156\n2 0 1463\n4 1 2439\n0 4 4373\n3 4 8889\n2 4 3133\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e71071\n54223\n\u003c/pre\u003e"}}]}