{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cdiv\u003e\u003cp\u003e拆除所有台阶后,新大陆在tgy的治理下蒸蒸日上,发展迅速,tgy也顺理成章地成为了世界滴神(?\u003cbr\u003e\n现在,tgy正准备策划一场大战,需要雇佣N名女猎人和M名男猎人,雇佣任何一名猎人的标准价格为10000金币。但事实上,女猎人和男猎人之间存在着一些不可名状的关系,这使得贫穷的tgy可以进一步降低征兵的成本,压榨剩余价值。如果女猎人x和男猎人y的关系系数为d,并且他们其中一个已经被tgy雇佣,那么tgy就能以10000-d金币的价格雇佣另外一个。雇佣一名猎人时只能使用最多一种关系作为折扣(别想白嫖\u003cbr\u003e\n现在,给出tgy想要雇佣的所有N名女猎人和M名男猎人之间的关系,请帮tgy计算雇佣他们所有人需要的最低成本\u003cbr\u003e\n请注意,作为kami,tgy并不认识万能头文件,请不要在本题使用\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cdiv\u003e\u003cp\u003e第一行输入一个正整数t,表示案例个数\u003cbr\u003e\n每组案例第一行包括3个正整数N,M,R,分别代表女猎人个数,男猎人个数和关系个数\u003cbr\u003e\n接下来的R行,每行包括3个正整数 xi, yi 和 di,分别表示第i个关系的女猎人序号、男猎人序号和折扣金币量\u003cbr\u003e\n相邻两组案例之间有一个空白行\u003cbr\u003e\n1 ≤ N, M ≤ 10000\u003cbr\u003e\n0 ≤ R ≤ 50,000\u003cbr\u003e\n0 ≤ xi \u003c N\u003cbr\u003e\n0 ≤ yi \u003c M\u003cbr\u003e\n0 \u003c di \u003c 10000\u003cbr\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e每组案例输出一行,为tgy征兵所需的最少成本\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"}}]}