{"trustable":false,"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":"PLAIN","content":"在赤壁之战中,曹操被诸葛亮和周瑜击败。但他不会放弃。曹操的军队仍然不善于水战,所以他提出了另一个想法。他在长江建造了许多岛屿,在这些岛屿的基础上,曹操的军队很容易攻击周瑜的部队。曹操还建造了连接岛屿的桥梁。如果所有岛屿都通过桥梁相连,那么曹操的军队可以在这些岛屿中非常方便地部署。周瑜无法忍受,所以他想要摧毁一些曹操的桥梁,这样一个或多个岛屿就会与其他岛屿分开。但周瑜只有一枚由诸葛亮留下的炸弹,所以他只能摧毁一座桥。周瑜必须派人携带炸弹来摧毁这座桥。桥上可能有守卫。轰炸队的士兵数量不能低于桥梁的守卫数量,否则任务就会失败。请弄清楚周瑜至少需要多少士兵。"}},{"title":"Input","value":{"format":"PLAIN","content":"测试用例不超过12个。 \n在每个测试用例中: \n第一行包含两个整数N和M,意味着有N个岛和M个桥。所有岛都从1到N编号。(2 \u003c\u003d N \u003c\u003d 1000,0 \u003cM \u003c\u003d N²) \n接下来的M行描述了M个桥。每条线包含三个整数U,V和W,意味着有一个连接岛U和岛V的桥,并且在该桥上有W守卫。(U≠V且0 \u003c\u003d W \u003c\u003d 10,000) \n输入以N \u003d 0且M \u003d 0结束。"}},{"title":"Output","value":{"format":"PLAIN","content":"对于每个测试用例,输出周瑜完成任务所需的最少士兵数量。如果周瑜无法成功,请输出-1。\n"}},{"title":"Sample Input","value":{"format":"PLAIN","content":"3 3\n1 2 7\n2 3 4\n3 1 4\n3 2\n1 2 7\n2 3 4\n0 0"}},{"title":"Sample Output","value":{"format":"PLAIN","content":"-1\n4"}}]}