CF721C Journey

近日，Irina 来到 Berland 最著名的城市之一 —— Berlatov 市。该市有 $n$ 个景点，编号从 $1$ 到 $n$，其中一些景点之间通过有向道路相连。Berlatov 市的道路设计使得任意景点之间不存在环路。 Irina 最初站在景点 $1$，她旅程的终点是景点 $n$。Irina 希望在旅途中尽可能多地参观景点。然而，Irina 在 Berlatov 的停留时间有限，她不能在那里逗留超过 $T$ 个时间单位。 请帮助 Irina 计算，在不超过 $T$ 的时间内，从景点 $1$ 到景点 $n$ 的途中，她最多可以参观多少个景点。 保证至少存在一条从景点 $1$ 到景点 $n$ 的路线，使 Irina 通行的总时间不超过 $T$。

输入的第一行为三个整数 $n, m, T$（$2 \le n \le 5000, 1 \le m \le 5000, 1 \le T \le 10^{9}$）——景点的数量、道路的数量以及 Irina 在 Berlatov 停留的最大时间。 接下来的 $m$ 行每行描述一条道路。第 $i$ 行包含三个整数 $u_i, v_i, t_i$（$1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le t_i \le 10^{9}$），表示有一条从景点 $u_i$ 通向景点 $v_i$ 的有向道路，Irina 通过它会花费 $t_i$ 个时间单位。保证这些道路不会构成环路。 保证任意一对景点之间至多一条道路。

输出一行一个整数 $k$（$2 \le k \le n$），表示 Irina 在不超过 $T$ 的时间内，从景点 $1$ 到景点 $n$ 的途中最多可以参观的景点数。 第二行输出 $k$ 个互不相同的整数，按访问顺序依次给出她会参观的景点编号。 如果有多种方案，输出任意一种均可。

由 ChatGPT 5 翻译