{"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在Henryy王国里,有N(2 \u0026lt;\u003d N \u0026lt;\u003d 200)个城市,有M(M \u0026lt;\u003d 30000)条单向道路连接它们。你有幸有机会在王国里旅游。路线应该设计为:路线应该包含一个或多个循环。(循环是一条路线,如:A-\u0026gt;B-\u0026gt;……-\u0026gt;P-\u0026gt;A。)\u003cbr\u003e每个城市应该只在一个路线中。\u003cbr\u003e一个循环应该至少有两个城市。在一个路线中,每个城市应该只被访问一次。(唯一的例外是第一个和最后一个城市应该相同,这个城市被访问两次。)\u003cbr\u003e你选择的N条道路的总距离应该最小。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行中的整数T表示测试用例的数量。\u003cbr\u003e在每个测试用例中,第一行包含两个整数N和M,表示城市数量和单向道路数量。然后是M行,每行有三个整数U、V和W(0 \u0026lt; W \u0026lt;\u003d 10000),表示从U到V有一条路,距离为W。\u003cbr\u003e保证至少存在一种有效的旅游安排。\u003cbr\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\u003e1\r\n6 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\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e42\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}