Problem Description

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.

Input Format

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 Format

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.

5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1

6

Hint

[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$.

Translated by ChatGPT 5