最近,伊琳娜抵达贝尔兰最著名的城市之一——贝尔拉托夫市。城市中有n个表演场所,编号从1到n,其中一些表演场所由单向道路连接。贝尔拉托夫的道路设计方式使得各表演场所之间没有循环路线。
最初伊琳娜站在秀场 1,她旅程的终点是秀场 n。当然,伊琳娜希望在旅途中尽可能多地参观名胜古迹。然而,伊琳娜在贝尔拉托夫的停留时间是有限的,她不能在那里停留超过T个时间单位。
帮助伊琳娜确定她在不超过T的时间内从秀场1到秀场n的旅程中可以访问多少个秀场。保证从秀场1到秀场n至少有一条路线,使得伊琳娜通过它的时间不超过T时间单位。
输入
输入的第一行包含三个整数 n、m 和 T (2 ≤ n ≤ 5000, 1 ≤ m ≤ 5000, 1 ≤ T ≤ 109)——分别是表演场所的数量、它们之间的道路数量以及伊琳娜在贝尔拉托夫停留的时间。
接下来的 m 行描述了贝尔拉托夫的道路。其中第i个包含3个整数ui,vi,ti(1≤ui,vi≤n,ui≠vi,1≤ti≤109),意味着有一条从showplace ui出发,通向showplace vi的路,Irina花了ti个时间单位通过它。确保道路不形成循环路线。
保证每对表演场所之间最多有一条路。
输出
在第一行中打印单个整数 k (2 ≤ k ≤ n) — 伊琳娜在不超过 T 的时间内从景点 1 到景点 n 的旅程中可以访问的景点的最大数量。
在第二行中打印 k 个不同的整数——伊琳娜将在路线上参观的景点的索引,按照遇到的顺序排列。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 3 13 1 2 5 2 3 7 2 4 8
输出 #1
3 1 2 4
输入 #2
6 6 7 1 2 2 1 3 3 3 6 3 2 4 2 4 6 2 6 5 1
输出 #2
4 1 2 4 6
输入 #3
5 5 6 1 3 3 3 5 3 1 2 2 2 4 3 4 5 2
输出 #3
3 1 3 5