Little Z plans to take a tour bus to visit a long-awaited scenic spot during the National Day holiday.

The map of the scenic spot has $n$ locations, connected by $m$ roads. Location $1$ is the entrance, and location $n$ is the exit. We denote the time the scenic spot opens as time $0$. Starting from time $0$, a tour bus arrives at the entrance every $k$ units of time, and simultaneously, a tour bus departs from the exit every $k$ units of time.

All roads are one-way. For each road, it takes exactly $1$ unit of time for a tourist to walk through it.

Little Z wishes to arrive at the entrance by tour bus, walk to the exit along a path of his choice, and then leave by tour bus. This means his arrival time at the entrance and departure time from the exit must both be non-negative integer multiples of $k$. Due to the large number of tourists during the holiday, Little Z only wants to keep moving along the scenic spot's roads before he leaves the scenic spot by tour bus, and does not want to linger at any location (including the entrance and exit) or on any road.

Before setting off, Little Z learns that the scenic spot has implemented a crowd control measure: each road has an "opening time" $a_i$, and tourists can only pass through this road at a time no earlier than $a_i$.

Please help Little Z design a travel plan such that the time he leaves the scenic spot by tour bus is as early as possible.

Input

The first line contains three positive integers $n, m, k$, representing the number of locations, the number of roads, and the departure interval of the tour buses, respectively.

The next $m$ lines each contain three non-negative integers $u_i, v_i, a_i$, representing that the $i$-th road goes from location $u_i$ to location $v_i$ and has an "opening time" of $a_i$.

Output

Output a single integer representing the earliest time Little Z can leave the scenic spot by tour bus. If no such travel plan exists, output $-1$.

Examples

Input 1

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

Output 1

6

Note 1

Figure 1: Example 1 illustration

Little Z can arrive at the entrance at time $3$, walk along the path $1 \to 3 \to 4 \to 5$, and leave at time $6$.

Input 2

See bus/bus2.in and bus/bus2.ans in the contestant's directory.

Constraints

For all test data: $2 \le n \le 10^4$, $1 \le m \le 2 \times 10^4$, $1 \le k \le 100$, $1 \le u_i, v_i \le n$, $0 \le a_i \le 10^6$.

Subtasks