{"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":"NE的膝盖疼得越来越严重了,于是他到了校医院要了一些药。经过医生的反向治疗之后,NE已经彻底走不了路了。他需要鸡尾酒和FF扶着他才能走路。但是NE太重了,鸡尾酒和FF体力有限,他们只能扶着NE走T米。现在NE从宿舍(记为点1)要去遥远的机房306(记为点n)讲线段树,NE希望能在鸡尾酒和FF的体力耗尽之前抵达306机房。\u003c/p\u003e\n\n\u003cp\u003e点1到点n之间还有n-2个其它点,代表学校沿途的风景。然而这n个点并不能随意互相到达,而是由一些单向路径连接。NE希望在他去机房的路上,能尽量多看几处风景。于是他想请你帮帮忙,给他设计一条路线,能尽可能多的看沿途的风景,但是总路径的长度小于T——不能累死鸡尾酒和FF啊!\u003c/p\u003e\n\n\u003cp\u003e保证从点1到点n的所有路径中,至少有一条路径的长度小于m。保证给出的图无环。"}},{"title":"Input","value":{"format":"HTML","content":"第一行给出n,m,T代表n个点,m条边,最长移动距离为T。(n,m\u003c5000,T\u003c1e9)\u003c/p\u003e\n\n\u003cp\u003e接下来有m行,每行给出u1,v1,t1,其中(1\u003c\u003du1,v1\u003c\u003dn)代表一条路径的两个端点,t1代表路径长度(t1\u003c1e9)\u003c/p\u003e\n\n\u003cp\u003e保证至少存在一条从1到n的路径,且路径长度小于T"}},{"title":"Output","value":{"format":"HTML","content":"先输出一行代表NE最多能看的风景数q(起点和终点也算风景,因为学习的机房是最好的风景)\u003c/p\u003e\n\n\u003cp\u003e然后第二行输出q个整数,代表一条从1到n的路径,起点为1,终点为n,每个数字中间用空格隔开。"}},{"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\u003e4 3 13\u003cbr\u003e1 2 5\u003cbr\u003e2 3 7\u003cbr\u003e2 4 8\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 4 \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\u003e6 6 7\u003cbr\u003e1 2 2\u003cbr\u003e1 3 3\u003cbr\u003e3 6 3\u003cbr\u003e2 4 2\u003cbr\u003e4 6 2\u003cbr\u003e6 5 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\u003e4\u003cbr\u003e1 2 4 6 \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\u003e5 5 6\u003cbr\u003e1 3 3\u003cbr\u003e3 5 3\u003cbr\u003e1 2 2\u003cbr\u003e2 4 3\u003cbr\u003e4 5 2\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 3 5 \u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"hint","value":{"format":"HTML","content":"对于样例1来说,可以看3个风景,分别为1,2,4,总时间消耗为5+8\u003d13"}}]}