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.
## Input
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.**
## Output
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.
[samples]
**Definitions:**
- Let $ G = (V, E) $ be a directed acyclic graph (DAG) with $ |V| = n $, $ |E| = m $.
- Vertices $ V = \{1, 2, \dots, n\} $ represent showplaces.
- Each edge $ (u, v) \in E $ has a weight $ t_{uv} \in \mathbb{Z}^+ $, representing time to traverse the road from $ u $ to $ v $.
- Source vertex: $ s = 1 $, target vertex: $ t = n $.
- Time constraint: $ T \in \mathbb{Z}^+ $, $ T \leq 10^9 $.
**Given:**
- $ G $ is a DAG with no cycles.
- There exists at least one path from $ s $ to $ t $ with total time $ \leq T $.
- Each pair of vertices has at most one directed edge between them.
**Objective:**
Find a path $ P = (v_0, v_1, \dots, v_k) $ such that:
- $ v_0 = 1 $, $ v_k = n $,
- $ \sum_{i=0}^{k-1} t_{v_i v_{i+1}} \leq T $,
- $ k $ (number of vertices visited, i.e., path length in vertices) is **maximized**.
**Formal Problem Statement:**
Maximize $ k $ subject to:
$$
\begin{aligned}
& \exists \text{ a path } P = (v_0, v_1, \dots, v_{k-1}) \text{ with } v_0 = 1, v_{k-1} = n, \\
& \sum_{i=0}^{k-2} t_{v_i v_{i+1}} \leq T, \\
& \text{and } k \text{ is as large as possible}.
\end{aligned}
$$
**Output:**
- Maximum number of showplaces visited: $ k $.
- A sequence $ v_0, v_1, \dots, v_{k-1} $ of distinct vertices forming such a path.
**Note:** Since $ G $ is a DAG, dynamic programming over topological order is feasible. Let $ dp[i][j] $ denote the minimum time required to reach vertex $ i $ while visiting exactly $ j $ showplaces. Then:
$$
dp[i][j] = \min_{(u,i) \in E} \left( dp[u][j-1] + t_{ui} \right), \quad \text{for } j \geq 2, i \in V \setminus \{1\}
$$
with base case $ dp[1][1] = 0 $, and $ dp[i][1] = \infty $ for $ i \ne 1 $.
Final answer: $ \max \{ j \mid dp[n][j] \leq T \} $, and reconstruct the path accordingly.