{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e曹操在赤壁之战中被诸葛亮和周瑜打败了。但他并没有放弃。曹操的军队仍然不擅长水战,所以他想出了另一个主意。他在长江上建造了许多岛屿,基于这些岛屿,曹操的军队可以轻松地攻击周瑜的部队。曹操还建造了连接岛屿的桥梁。如果所有岛屿都被桥梁连接起来,曹操的军队可以在这些岛屿之间非常方便地部署。周瑜无法忍受这种情况,所以他想摧毁一些曹操的桥梁,使一个或多个岛屿与其他岛屿分离。但周瑜只有一颗被诸葛亮留下的炸弹,所以他只能炸毁一座桥梁。周瑜必须派人携带炸弹去摧毁桥梁。桥上可能有守卫。炸桥小队的士兵数量不能少于桥上的守卫数量,否则任务将失败。请计算出周瑜至少需要派遣多少士兵才能完成分离岛屿的任务。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"每个测试用例不超过12个。\u003cbr\u003e\u003cbr\u003e在每个测试用例中:\u003cbr\u003e\u003cbr\u003e第一行包含两个整数N和M,表示有N个岛屿和M座桥。所有岛屿从1到N编号。(2 ≤ N ≤ 1000,0 ≤ M ≤ N\u003csup\u003e2\u003c/sup\u003e)\u003cbr\u003e\u003cbr\u003e接下来的M行描述M座桥。每行包含三个整数U、V和W,表示连接岛屿U和岛屿V的桥梁,桥上有W名守卫。(U ≠ V且0 ≤ W ≤ 10,000)\u003cbr\u003e\u003cbr\u003e输入以N \u003d 0和M \u003d 0结束。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,打印周瑜需要派遣的最少士兵数量以完成任务。如果周瑜无论如何都无法成功,打印-1。"}},{"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\u003e3 3\r\n1 2 7\r\n2 3 4\r\n3 1 4\r\n3 2\r\n1 2 7\r\n2 3 4\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}