题目描述

小明计划从城市 $1$ 出发，前往城市 $n$ 旅行。沿途共有 $n$ 座城市，编号为 $1 \sim n$。城市之间由 $m$ 条单向道路相连，任意两座城市之间至多有一条道路，且这些道路不会构成环路——也就是说，无论怎么走，都不可能回到已经访问过的城市。

每条道路通过需要花费一定时间。小明从城市 $1$ 出发，必须在总时间不超过 $T$ 的情况下到达目的地城市 $n$。他希望在这段旅途中能够访问尽可能多的城市（起点和终点均计入访问数量）。

请帮助小明计算：在总时间不超过 $T$ 的前提下，从城市 $1$ 到城市 $n$ 最多可以访问多少座城市，并给出一条可行的访问路线。

题目保证：至少存在一条从城市 $1$ 到城市 $n$ 的路径，使得总时间不超过 $T$。

输入格式

第一行包含三个整数 $n, m, T$，分别表示城市的数量、道路的数量和允许的最大总时间。

接下来 $m$ 行，每行包含三个整数 $u_i, v_i, t_i$，表示一条从城市 $u_i$ 到城市 $v_i$ 的单向道路，通过时间为 $t_i$。

输出格式

第一行输出一个整数 $k$，表示最多可以访问的城市数量。

第二行输出 $k$ 个空格分隔的整数，依次表示访问的城市编号。如果有多种方案，输出任意一种均可。

样例 #1

4 4 10
1 2 2
1 3 3
2 4 4
3 4 8

3
1 2 4

样例解释 #1

所有可能的路线：

• $1 \to 2 \to 4$，经过 $3$ 座城市，用时 $2+4=6 \le 10$；
• $1 \to 3 \to 4$，经过 $3$ 座城市，用时 $3+8=11 > 10$（超时）。

因此最多可以访问 $3$ 座城市，路线 $1 \to 2 \to 4$ 是唯一可行方案。

样例 #2

6 6 4
1 2 1
2 3 1
1 4 1
3 5 1
4 5 1
5 6 1

5
1 2 3 5 6

样例解释 #2

该样例满足特殊性质：所有道路的通过时间均为 $1$。此时总时间不超过 $T$ 等价于经过的道路数不超过 $T$。

路线 $1 \to 2 \to 3 \to 5 \to 6$ 经过 $5$ 座城市，用时 $4 \le 4$，是最优方案。

样例 #3

点击链接 ex_travel3.in 和 ex_travel3.ans 下载大样例 3 的输入数据和输出数据。

该样例满足子任务 5 的约束（无特殊性质，$n = 5000$，$m = 5000$）。

数据范围

对于所有测试数据，保证：

• $2 \le n \le 5000$，$1 \le m \le 5000$；
• $1 \le T \le 10^9$；
• $1 \le u_i, v_i \le n$，$u_i \ne v_i$；
• $1 \le t_i \le 10^9$；
• 道路构成一个有向无环图，且任意两座城市之间至多有一条道路；
• 至少存在一条从城市 $1$ 到城市 $n$ 的路径，其总时间不超过 $T$。

每个测试点独立计分，共 $20$ 个测试点，每个测试点 $5$ 分。各测试点的特殊性质如下：

说明：每个子任务的测试点仅保证满足对应列出的特殊性质，不一定满足其他子任务的性质。例如子任务 3 的测试点仅有入度 $\le 1$ 的性质，不一定存在链。

时间限制 $3$ 秒，空间限制 $512$ MB。

提示

• 子任务 1：$n$ 很小，可以暴力枚举所有可能的路径。
• 子任务 2：时间约束退化为「经过的道路数不超过 $T$」，无需考虑不同的边权。
• 子任务 3：到达每座城市的路径唯一，无需在多种方案之间比较。
• 子任务 4：链的存在使得处理顺序天然确定。
• 子任务 5：需要完整的动态规划。建议使用 long long 存储累积时间。