{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e温迪有一个国家,他想建立一支军队来保护他的国家。他已经挑选了\u003ci\u003eN\u003c/i\u003e个女孩和\u003ci\u003eM\u003c/i\u003e个男孩,并希望收集他们成为他的士兵。要收集一个没有特权的士兵,他必须支付10000人民币。女孩和男孩之间存在一些关系,温迪可以利用这些关系来降低成本。如果女孩\u003cb\u003ex\u003c/b\u003e和男孩\u003cb\u003ey\u003c/b\u003e之间有一个关系\u003ci\u003ed\u003c/i\u003e,并且其中一个已经被收集,温迪可以以10000-\u003ci\u003ed\u003c/i\u003e人民币的价格收集另一个。现在给出所有女孩和男孩之间的关系,请你找出温迪需要支付的最少金额。请注意,每次收集一个士兵时只能使用一个关系。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e输入的第一行是测试用例的数量。\u003cbr\u003e每个测试用例的第一行包含三个整数,\u003ci\u003eN\u003c/i\u003e、\u003ci\u003eM\u003c/i\u003e和\u003ci\u003eR\u003c/i\u003e。\u003cbr\u003e然后是\u003ci\u003eR\u003c/i\u003e行,每行包含三个整数\u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e、\u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e和\u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e。\u003cbr\u003e每个测试用例之前有一个空行。\u003cbr\u003e\u003c/p\u003e\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\u003c/div\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一个单独的行表示答案。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\r\n5 5 8\r\n4 3 6831\r\n1 3 4583\r\n0 0 6592\r\n0 1 3063\r\n3 3 4975\r\n1 3 2049\r\n4 2 2104\r\n2 2 781\r\n\r\n5 5 10\r\n2 4 9820\r\n3 2 6236\r\n3 1 8864\r\n2 4 8326\r\n2 0 5156\r\n2 0 1463\r\n4 1 2439\r\n0 4 4373\r\n3 4 8889\r\n2 4 3133\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e71071\r\n54223\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}