{"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\u003eBreaking Good is a new video game which a lot of gamers want to have. There is a certain level in the game that is really difficult even for experienced gamers.\u003c/p\u003e\u003cp\u003eWalter William, the main character of the game, wants to join a gang called Los Hermanos (The Brothers). The gang controls the whole country which consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e cities with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e bidirectional roads connecting them. There is no road is connecting a city to itself and for any two cities there is at most one road between them. The country is connected, in the other words, it is possible to reach any city from any other city using the given roads. \u003c/p\u003e\u003cp\u003eThe roads aren\u0027t all working. There are some roads which need some more work to be performed to be completely functioning.\u003c/p\u003e\u003cp\u003eThe gang is going to rob a bank! The bank is located in city \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. As usual, the hardest part is to escape to their headquarters where the police can\u0027t get them. The gang\u0027s headquarters is in city \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. To gain the gang\u0027s trust, Walter is in charge of this operation, so he came up with a smart plan.\u003c/p\u003e\u003cp\u003eFirst of all the path which they are going to use on their way back from city \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to their headquarters \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e must be \u003cspan class\u003d\"tex-font-style-underline\"\u003eas short as possible\u003c/span\u003e, since it is important to finish operation as fast as possible.\u003c/p\u003e\u003cp\u003eThen, gang has to blow up all other roads in country that don\u0027t lay on this path, in order to prevent any police reinforcements. In case of non-working road, they don\u0027t have to blow up it as it is already malfunctional. \u003c/p\u003e\u003cp\u003eIf the chosen path has some roads that doesn\u0027t work they\u0027ll have to repair those roads before the operation.\u003c/p\u003e\u003cp\u003eWalter discovered that there was a lot of paths that satisfied the condition of being shortest possible so he decided to choose among them a path that minimizes the total number of affected roads (both roads that have to be blown up and roads to be repaired).\u003c/p\u003e\u003cp\u003eCan you help Walter complete his task and gain the gang\u0027s trust?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/e02cdcc56cabc6d568e38220ba2a3fce?v\u003d1716094735\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e), the number of cities and number of roads respectively.\u003c/p\u003e\u003cp\u003eIn following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines there are descriptions of roads. Each description consists of three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e, \u003ci\u003ez\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/bfc817d984247a40d50b5433711190f6?v\u003d1716094735\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e) meaning that there is a road connecting cities number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e. If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e \u003d 1\u003c/span\u003e, this road is working, otherwise it is not.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn the first line output one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e, the minimum possible number of roads affected by gang.\u003c/p\u003e\u003cp\u003eIn the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e lines output three integers describing roads that should be affected. Each line should contain three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e, \u003ci\u003ez\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/bfc817d984247a40d50b5433711190f6?v\u003d1716094735\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e), cities connected by a road and the new state of a road. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e \u003d 1\u003c/span\u003e indicates that the road between cities \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e should be repaired and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e \u003d 0\u003c/span\u003e means that road should be blown up. \u003c/p\u003e\u003cp\u003eYou may output roads in any order. Each affected road should appear exactly once. You may output cities connected by a single road in any order. If you output a road, it\u0027s original state should be different from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eAfter performing all operations accroding to your plan, there should remain working only roads lying on some certain shortest past between city \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIf there are multiple optimal answers output any.\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\u003e2 1\n1 2 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e4 4\n1 2 1\n1 3 0\n2 3 1\n3 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2 0\n1 3 1\n2 3 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e8 9\n1 2 0\n8 3 0\n2 3 1\n1 4 1\n8 7 0\n1 5 1\n4 6 1\n5 7 0\n6 8 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2 3 0\n1 5 0\n6 8 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test the only path is \u003cspan class\u003d\"tex-span\"\u003e1 - 2\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIn the second test the only shortest path is \u003cspan class\u003d\"tex-span\"\u003e1 - 3 - 4\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIn the third test there are multiple shortest paths but the optimal is \u003cspan class\u003d\"tex-span\"\u003e1 - 4 - 6 - 8\u003c/span\u003e\u003c/p\u003e"}}]}