{"trustable":false,"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":"\u003c/pre\u003e\n最近小G玩《杀手》有些上头,天天打到半夜以至于白天昏昏沉沉的。某天早上第一节是组原课,小G听着听着又犯困了,为了让自己精神起来专心听课,他打开了游戏。\u003c/p\u003e\n这次的任务是刺杀某黑帮老大,由于小G技艺非凡,刺杀任务不在话下,但是逃跑成了大问题。黑帮的基地建在一个废弃的无人区,无人区有N个要塞,道路有好有坏,整个区域可以看成是一张联通的无向图(连通性与道路好坏无关),黑帮基地位于点1,安全区位于点N,假设你已经完成了刺杀任务,打算逃回安全区,很显然选择时间越短的路对自己的逃跑越有帮助,所以你提前制定了一条逃跑路线,这条路线上每条道路必须是好的(如果不好,需要提前维修),除了逃跑路线以外的路,都要被炸掉,防止敌方支援。现在让你找到这样一条路,他是最短的,并且路径上受影响的路的数量最小,请输出你的方案吧!"}},{"title":"Input","value":{"format":"HTML","content":"\u003c/pre\u003e\n输入第一行两个整数N,M(2\u003c\u003dN\u003c\u003d1e5,0\u003c\u003dM\u003c\u003dmin(1e5,N*(N-1)/2)),分别表示无人区的要塞数和道路数,接下来M行,每行三个整数u,v,w,表示连接该边的两个要塞,和这条边的情况(1表示好,0表示不好)。"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/pre\u003e\n输出第一行一个整数K,表示受影响的道路数,接下来K行,每行三个整数u,v,w,u和v表示要塞,w\u003d0表示这条边需要被摧毁,w\u003d1表示这条边需要被修复。"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e2 1\u003cbr\u003e1 2 0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e1\u003cbr\u003e1 2 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 4\u003cbr\u003e1 2 1\u003cbr\u003e1 3 0\u003cbr\u003e2 3 1\u003cbr\u003e3 4 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e3\u003cbr\u003e1 2 0\u003cbr\u003e1 3 1\u003cbr\u003e2 3 0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e8 9\u003cbr\u003e1 2 0\u003cbr\u003e8 3 0\u003cbr\u003e2 3 1\u003cbr\u003e1 4 1\u003cbr\u003e8 7 0\u003cbr\u003e1 5 1\u003cbr\u003e4 6 1\u003cbr\u003e5 7 0\u003cbr\u003e6 8 0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e3\u003cbr\u003e2 3 0\u003cbr\u003e1 5 0\u003cbr\u003e6 8 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003c/pre\u003e\n三个测试样例选择的路径分别为:\u003c/p\u003e\n1-\u003e2\u003c/p\u003e\n1-\u003e3-\u003e4\u003c/p\u003e\n1-\u003e4-\u003e6-\u003e8(有多条最短路,但是本条路径受影响数最少)\u003c/p\u003e"}}]}