← 返回题目列表

Codeforces · 721/C

C. 旅程

中文机器翻译题面 查看原题

最近,伊琳娜抵达贝尔兰最著名的城市之一——贝尔拉托夫市。城市中有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