{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMany may think: \"What will I do in Yekaterinburg? This city is in the end of the world!!\". However, many important things have happened in this city, so it has many monuments and historical places. To name a few, Yekaterinburg has a monument that is a huge computer keyboard located in the banks of river Izet; a monument to Michael Jackson (!!); in the Ipatiev mansion some Romanovs were murdered (czar Nicolau, his wife and children); also there was an anthrax leak in 1979; an american U2 pilot was captured and convicted for espionage; among others. Therefore, there is plenty to do in the city.\u003c/p\u003e\u003cp\u003eYekaterinburg\u0027s tourism central built a map with all the main tourist attractions in the city, as well as beautiful excursions connecting these attractions. This map also shows a difficulty level for each excursion (taking in account duration, paving of the streets, etc.) and the direction in which it should be traversed.\u003c/p\u003e\u003cp\u003eThey wish to build a route that goes through all the tourist attractions and excursions. A contest was made to create this route, and also to honor one of the sister cities of Yekaterinburg: Kaliningrad, that was named Königsberg until the end of the second world war. The idea was to build a route that started in one of the attractions, and going through all excursions returned to the starting point.\u003c/p\u003e\u003cp\u003eWe know that, as in the case of the bridges of Königsberg, it isn\u0027t always possible to build such route. That\u0027s why the central allowed excursions to be traversed more than once, if necessary. However, the central required that the total difficulty of the route (the sum of the difficulties of each excursion in it, counting repetitions) was minimal.\u003c/p\u003e\u003cp\u003eYour task is to find this minimal total difficulty, or determine if there exists no such route.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eOn the first line \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e, the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case has two integers\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e and\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e, the number of tourist attractions and the number of excursions, respectively. The\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of the next\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines has three integers\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e,\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, meaning the\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th excursion starts at\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, ends at\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and has difficulty\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eLimits\u003c/span\u003e \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ 100\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 50\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003eM\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e2\u003c/sup\u003e + 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003eN\u003c/i\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 3·10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e The sum of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e over all test cases won\u0027t exceed 1500. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print the minimal total difficulty of the desired route. If there is no such route, print \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eThe answer may not fit in a 32-bit integer.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Examples","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\u003e3\n2 2\n1 2 10000\n2 1 30000\n4 7\n1 2 1\n2 1 2\n2 3 4\n2 3 4\n3 2 3\n3 4 10\n4 3 100\n3 2\n1 2 1000\n2 3 1000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40000\n127\n-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}