CF721C.Journey

Recently Irina arrived to one of the most famous cities of Berland — the Berlatov city. There are n showplaces in the city, numbered from 1 to n, and some of them are connected by one-directional roads. The roads in Berlatov are designed in a way such that there are no cyclic routes between showplaces.

Initially Irina stands at the showplace 1, and the endpoint of her journey is the showplace n. Naturally, Irina wants to visit as much showplaces as she can during her journey. However, Irina's stay in Berlatov is limited and she can't be there for more than T time units.

Help Irina determine how many showplaces she may visit during her journey from showplace 1 to showplace n within a time not exceeding T. It is guaranteed that there is at least one route from showplace 1 to showplace n such that Irina will spend no more than T time units passing it.

最近，伊琳娜来到了贝尔兰德最著名的城市之一——贝尔拉托夫市。该市共有 $n$ 个景点，编号从 $1$ 到 $n$，其中一些景点由单向道路连接。贝尔拉托夫市的道路设计保证了景点之间不存在环路。

初始时，伊琳娜位于景点 $1$，而她旅程的终点是景点 $n$。显然，伊琳娜希望在旅途中尽可能多地参观景点。然而，伊琳娜在贝尔拉托夫市的停留时间有限，总耗时不能超过 $T$ 个时间单位。

请帮助伊琳娜确定：在从景点 $1$ 到景点 $n$ 的旅途中，她最多能参观多少个景点，且总耗时不超过 $T$？题目保证至少存在一条从景点 $1$ 到景点 $n$ 的路径，其总耗时不超过 $T$。

The first line of the input contains three integers n, m and T (2 ≤ n ≤ 5000,  1 ≤ m ≤ 5000,  1 ≤ T ≤ 109) — the number of showplaces, the number of roads between them and the time of Irina's stay in Berlatov respectively.

The next m lines describes roads in Berlatov. i-th of them contains 3 integers u__i, v__i, t__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i, 1 ≤ t__i ≤ 109), meaning that there is a road starting from showplace u__i and leading to showplace v__i, and Irina spends t__i time units to pass it. It is guaranteed that the roads do not form cyclic routes.

It is guaranteed, that there is at most one road between each pair of showplaces.

输入的第一行包含三个整数 $n$、$m$ 和 $T$（$2 \le n \le 5000$，$1 \le m \le 5000$，$1 \le T \le 10^9$），分别表示景点的数量、景点之间的道路数量，以及伊琳娜在贝尔拉托夫的停留时间。

接下来的 $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$ 的道路，伊琳娜通过该道路需耗时 $t_i$ 个时间单位。保证这些道路不构成环路。

保证任意两个景点之间至多只有一条道路。

Print the single integer k (2 ≤ k ≤ n) — the maximum number of showplaces that Irina can visit during her journey from showplace 1 to showplace n within time not exceeding T, in the first line.

Print k distinct integers in the second line — indices of showplaces that Irina will visit on her route, in the order of encountering them.

If there are multiple answers, print any of them.

在第一行输出单个整数 $k$（$2 \leq k \leq n$）—— 表示伊琳娜在从景点 1 到景点 $n$ 的旅途中，于总耗时不超过 $T$ 的前提下，最多能够参观的景点数量。

在第二行输出 $k$ 个互不相同的整数—— 表示伊琳娜在行程中将参观的景点编号，按其被访问的顺序排列。

若存在多个合法答案，输出任意一个即可。