P9751 [CSP-J 2023] Tourist Bus.

Xiao Z plans to take a tourist bus to visit a scenic spot he has long wanted to see during the National Day holiday. The map of the scenic area has a total of $n$ locations, with $m$ roads connecting them. Location $1$ is the entrance of the scenic area, and location $n$ is the exit. We define the opening time of the scenic area in a day as time $0$. Starting from time $0$, every $k$ units of time, a tourist bus arrives at the entrance, and at the same time a tourist bus departs from the exit. All roads are **one-way only**. For each road, walking through it takes exactly $1$ unit of time. Xiao Z wants to take a tourist bus to arrive at the entrance, walk along any path of his choice to reach the exit, and then take a tourist bus to leave. This means that both his arrival time and departure time must be **non-negative multiples of $k$**. Because there are many tourists during holidays, **before the tourist bus leaves the scenic area, Xiao Z only wants to keep moving along the roads, and does not want to wait at any location (including the entrance and exit) or on any road**. Before leaving, Xiao Z suddenly learns that the scenic area limits visitor flow: each road has an “opening time” $a _ i$, and visitors can pass through this road only **at times not earlier than $a _ i$**. Please help Xiao Z design a travel plan so that the time when he leaves the scenic area by tourist bus is as early as possible.

The first line contains $3$ positive integers $n, m, k$, representing the number of locations, the number of roads, and the departure interval of the tourist buses. The next $m$ lines each contain $3$ non-negative integers $u _ i, v _ i, a _ i$, indicating that the $i$-th road starts from location $u _ i$, ends at location $v _ i$, and has an “opening time” of $a _ i$.

Output one line containing only one integer, which is the earliest time when Xiao Z can take a tourist bus to leave the scenic area. If there is no feasible travel plan, output `-1`.

**[Sample #1 Explanation]** Xiao Z can arrive at the entrance at time $3$, walk to the exit in the order $1 \to 3 \to 4 \to 5$, and leave at time $6$. **[Sample #2]** See `bus/bus2.in` and `bus/bus2.ans` in the attachment. **[Constraints]** For all testdata: $2 \leq n \leq 10 ^ 4$, $1 \leq m \leq 2 \times 10 ^ 4$, $1 \leq k \leq 100$, $1 \leq u _ i, v _ i \leq n$, $0 \leq a _ i \leq 10 ^ 6$. | Test Point ID | $n \leq$ | $m \leq$ | $k \leq$ | Special Property | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $10$ | $15$ | $100$ | $a _ i = 0$ | | $3 \sim 5$ | $10$ | $15$ | $100$ | None | | $6 \sim 7$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $1$ | $a _ i = 0$ | | $8 \sim 10$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $1$ | None | | $11 \sim 13$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $100$ | $a _ i = 0$ | | $14 \sim 15$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $100$ | $u _ i \leq v _ i$ | | $16 \sim 20$ | $10 ^ 4$ | $2 \times 10 ^ 4$ | $100$ | None | Translated by ChatGPT 5