{"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我们国家有N个城市,它们之间有M条单向道路相连。现在小汤姆想要进行多次循环旅行,要求每个循环包含至少两个城市,并且每个城市恰好属于一个循环。汤姆希望所有旅行的总长度最小,但他懒得计算。你能帮帮他吗?\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例,直到文件结束为止 (EOF)。\u003cbr\u003e每个测试用例的第一行包含两个整数N (N ≤ 100)和M,表示城市的数量和道路的数量。接下来的M行,每行包含三个整数A、B和C,表示从城市A到城市B有一条长度为C的道路。(1 ≤ A,B ≤ N, A ≠ B, 1 ≤ C ≤ 1000)。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对每个测试用例输出一个数字,表示所有旅行的最小长度。如果不存在这样的旅行,则输出-1。\u003cbr\u003e"}},{"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\u003e6 9\r\n1 2 5\r\n2 3 5\r\n3 1 10\r\n3 4 12\r\n4 1 8\r\n4 6 11\r\n5 4 7\r\n5 6 9\r\n6 5 4\r\n6 5\r\n1 2 1\r\n2 3 1\r\n3 4 1\r\n4 5 1\r\n5 6 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e42\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"在第一个样例中,有两个循环,(1-\u003e2-\u003e3-\u003e1) 和 (6-\u003e5-\u003e4-\u003e6),它们的长度分别为20 + 22 \u003d 42。"}}]}