{"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\"\u003eIn the kingdom of Henryy, there are N (2 \u0026lt;\u003d N \u0026lt;\u003d 200) cities, with M (M \u0026lt;\u003d 30000) one-way roads connecting them. You are lucky enough to have a chance to have a tour in the kingdom. The route should be designed as: The route should contain one or more loops. (A loop is a route like: A-\u0026gt;B-\u0026gt;……-\u0026gt;P-\u0026gt;A.)\u003cbr\u003eEvery city should be just in one route.\u003cbr\u003eA loop should have at least two cities. In one route, each city should be visited just once. (The only exception is that the first and the last city should be the same and this city is visited twice.)\u003cbr\u003eThe total distance the N roads you have chosen should be minimized.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"An integer T in the first line indicates the number of the test cases.\u003cbr\u003eIn each test case, the first line contains two integers N and M, indicating the number of the cities and the one-way roads. Then M lines followed, each line has three integers U, V and W (0 \u0026lt; W \u0026lt;\u003d 10000), indicating that there is a road from U to V, with the distance of W.\u003cbr\u003eIt is guaranteed that at least one valid arrangement of the tour is existed.\u003cbr\u003eA blank line is followed after each test case."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output a line with exactly one integer, which is the minimum total distance."}},{"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\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\n"}}]}