{"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是一款新的视频游戏,许多玩家都想要拥有。游戏中有一个特定的关卡,即使是经验丰富的玩家也觉得非常困难。\u003c/p\u003e\u003cp\u003e游戏的主角Walter William想要加入一个名为Los Hermanos(兄弟会)的帮派。这个帮派控制着整个国家,该国家由\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e个城市和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e条双向道路连接而成。没有一条道路连接一个城市到自己,对于任意两个城市之间最多只有一条道路相连。换句话说,这个国家是连通的,也就是说可以使用给定的道路从任意一个城市到达另一个城市。\u003c/p\u003e\u003cp\u003e这些道路并不都是畅通无阻的。有一些道路需要进行一些工作才能完全发挥作用。\u003c/p\u003e\u003cp\u003e这个帮派打算抢劫一家银行!这家银行位于城市\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e。像往常一样,最困难的部分是逃到他们的总部,让警察束手无策。这个帮派的总部位于城市\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e。为了赢得帮派的信任,Walter负责这次行动,所以他想出了一个聪明的计划。\u003c/p\u003e\u003cp\u003e首先,他们从城市\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e返回总部\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e的路径必须\u003cspan class\u003d\"tex-font-style-underline\"\u003e尽可能短\u003c/span\u003e,因为尽快完成行动非常重要。\u003c/p\u003e\u003cp\u003e然后,帮派必须炸毁所有不在这条路径上的国家中的其他道路,以防止任何警察增援。如果选择的路径上有一些不通畅的道路,他们就必须在行动前修复这些道路。\u003c/p\u003e\u003cp\u003eWalter发现有很多路径都满足了尽可能短的条件,所以他决定在这些路径中选择一个最小化受影响的道路总数(需要炸毁和需要修复的道路总数)的路径。\u003c/p\u003e\u003cp\u003e你能帮助Walter完成他的任务,赢得帮派的信任吗?\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含两个整数\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\u003d1711136346\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e),分别表示城市的数量和道路的数量。\u003c/p\u003e\u003cp\u003e接下来的\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e行描述了道路。每个描述由三个整数\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\u003d1711136346\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e)组成,表示连接城市编号\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e的道路。如果\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e \u003d 1\u003c/span\u003e,则这条道路是通畅的,否则就是不通畅的。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e在第一行输出一个整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e,表示帮派可能受到的最小影响的道路数量。\u003c/p\u003e\u003cp\u003e接下来的\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e行输出描述受影响的道路的三个整数。每行应包含三个整数\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\u003d1711136346\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e),表示一条道路连接的城市和道路的新状态。 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e \u003d 1\u003c/span\u003e表示应该修复城市\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e之间的道路,\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e \u003d 0\u003c/span\u003e表示应该炸毁这条道路。\u003c/p\u003e\u003cp\u003e你可以以任何顺序输出道路。每条受影响的道路应该仅出现一次。你可以以任何顺序输出一条道路连接的城市。如果你输出一条道路,它的原始状态应该与\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e\u003c/span\u003e不同。\u003c/p\u003e\u003cp\u003e根据你的计划执行所有操作后,应该只保留连接城市\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e之间某条特定最短路径上的通畅道路。\u003c/p\u003e\u003cp\u003e如果有多个最优解,输出任意一个。\u003c/p\u003e"}},{"title":"示例1","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"}},{"title":"示例2","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"}},{"title":"示例3","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"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试中,唯一的路径是\u003cspan class\u003d\"tex-span\"\u003e1 - 2\u003c/span\u003e\u003c/p\u003e\u003cp\u003e在第二个测试中,唯一的最短路径是\u003cspan class\u003d\"tex-span\"\u003e1 - 3 - 4\u003c/span\u003e\u003c/p\u003e\u003cp\u003e在第三个测试中,有多条最短路径,但最优解是\u003cspan class\u003d\"tex-span\"\u003e1 - 4 - 6 - 8\u003c/span\u003e\u003c/p\u003e"}}]}