{"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 “关系”是中文中非常重要的一个词。它有点像“关系”或“联系”的意思。关系可以建立在友谊基础上,也可以建立在金钱基础上。所以中国人经常说“我和你没有一毛钱的关系。”或者“他们之间的关系是赤裸裸的金钱关系。”据说中国社会是一个关系社会,所以你可以看到关系在很多事情中扮演着非常重要的角色。\u003cbr\u003e\u003cbr\u003e 这里有一个例子。在中国的许多城市,政府禁止中学入学考试,以减轻小学生的学习负担。因为入学标准不明确且不严格,有些人可能通过关系让他们的孩子进入好的中学。刘老板想要通过关系让他的孩子今年上中学。所以他找到了他的关系网。刘老板的关系网包括N个人,包括刘老板和校长。在这个网中,有关系的两个人可以互相帮助。因为刘老板是个有钱人(在中国英语中,“有钱人”指的是有很多钱的人)而且朋友不多,他的关系网是一个赤裸裸的金钱关系网——这意味着如果A和B之间有关系,A帮助B时必须得到报酬。通过他的关系网,刘老板可以请求A帮助他,然后A可以请求B帮助,然后B可以请求C帮助……如果请求最终到达校长,刘老板的孩子将被中学录取。当然,包括校长在内的所有帮助者都会得到刘老板的报酬。\u003cbr\u003e\u003cbr\u003e 你讨厌刘老板,你想破坏刘老板的计划。你所能做的就是说服刘老板的关系网中的一个人拒绝任何请求。这个人可以是任何一个,但不能是刘老板或校长。如果你不能让刘老板失败,你希望刘老板花费的钱越多越好。你应该计算出在你尽力之后,刘老板至少要花多少钱才能得到他想要的。请注意,如果你什么都不做,刘老板肯定会成功。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"有多个测试用例。\u003cbr\u003e\u003cbr\u003e 对于每个测试用例:\u003cbr\u003e\u003cbr\u003e 第一行包含两个整数N和M。N表示刘老板的关系网中有N个人。他们的编号从1到N。刘老板是1号,校长是N号。M表示刘老板的关系网中有M个关系。(3 ≤ N ≤ 30, 3 ≤ M ≤ 1000)\u003cbr\u003e\u003cbr\u003e 然后是M行。每行包含三个整数A、B和C,表示A和B之间有关系,如果A请求B或B请求A帮助,帮助者将得到刘老板支付的C元人民币。\u003cbr\u003e\u003cbr\u003e 输入以N \u003d 0和M \u003d 0结束。\u003cbr\u003e\u003cbr\u003e 保证如果你不试图破坏他的计划,刘老板的请求一定会到达校长那里。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,输出你尽力之后刘老板至少要花多少钱才能得到他想要的。如果刘老板无法让他的孩子上中学,输出“Inf”。"}},{"title":"Sample","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\u003e4 5\r\n1 2 3\r\n1 3 7\r\n1 4 50\r\n2 3 4\r\n3 4 2\r\n3 2\r\n1 2 30\r\n2 3 10\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e50\r\nInf\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}