Quickest Tourist Exit

During the National Day holiday, Little Z plans to ride a tourist bus to visit a long‐dreamed-of scenic spot. The map of the scenic area consists of \(n\) locations and \(m\) one-way roads. The entrance is at location 1 and the exit is at location \(n\). The scenic area opens at time 0. Starting from time 0, every \(k\) units of time a bus arrives at the entrance, and at the same time a bus leaves the exit.

Little Z will take a bus arriving exactly at a nonnegative integer multiple of \(k\) to reach the entrance, and then he will walk through a path (without ever waiting at any vertex or on any road) to reach the exit, where he immediately catches a bus departing at a nonnegative integer multiple of \(k\). Note that if he starts at time \(T_0\) (a multiple of \(k\)) and walks along a path of length \(L\) (each road takes exactly 1 unit of time), his arrival time at a road is \(T_0, T_0+1, \ldots, T_0+L-1\) and his exit time will be \(T_0+L\). To be able to traverse a road, its "open time" requirement must be met: for a road with open time \(a_i\), you can only pass it if the current time is not less than \(a_i\). In other words, if the road is taken as the \(j\)th road (0-indexed) on your path, you must have

\(T_0 + j \ge a_i\).

Furthermore, since both the boarding time at the entrance and the departure time at the exit are multiples of \(k\), if you take a path with \(L\) edges starting at time \(T_0\), then \(T_0+L\) must also be a multiple of \(k\). Equivalently, the number of roads traversed \(L\) must be a multiple of \(k\).

Your task is to help Little Z design a travel plan so that he can leave the scenic area as early as possible. If it is impossible to design such a plan, output -1.

Hint: For any chosen valid path \(P\) of length \(L\) (where \(L\) is a multiple of \(k\)), if the road taken at the \(j\)th position (0-indexed) has an open time \(a_{e_j}\), then the starting time must satisfy

\(T_0 \ge \max_{0 \le j < L} (a_{e_j} - j, \; 0)\).

The minimum exit time for that path is then \(T_0 + L\), where \(T_0\) is the smallest multiple of \(k\) not less than \(\max_{0 \le j < L}(a_{e_j} - j,0)\). You need to choose both the bus departure time at the entrance and a valid path so that the exit time is minimized.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\) \((2 \le n \le 10^5,\; 1 \le m \le 10^5,\; 1 \le k \le 10^9)\) representing the number of locations, the number of roads, and the bus interval respectively.

Then \(m\) lines follow. Each of these lines contains three integers \(u\), \(v\) and \(a_i\) \((1 \le u,v \le n,\; 0 \le a_i \le 10^9)\) indicating there is a one-way road from location \(u\) to location \(v\) that can only be used at time \(t\) if \(t \ge a_i\).

outputFormat

Output a single integer representing the earliest possible exit time Little Z can achieve. If it is impossible to design a plan meeting the requirements, output -1.

sample

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

3