H. Highest Median Walk
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a weighted directed graph with $$$n$$$ vertices and $$$m$$$ edges. The $$$i^\text{th}$$$ edge is directed from vertex $$$u_i$$$ to vertex $$$v_i$$$ and has weight $$$w_i$$$. Find the maximum possible median of a walk with length at least $$$k$$$.

A walk of length $$$s$$$ is a sequence of (not necessarily distinct) edges $$$e_1, e_2, \dots, e_s$$$ for which there exists a sequence of vertices $$$p_1, p_2, \dots, p_{s+1}$$$ such that the edge $$$e_j$$$ is directed from $$$p_j$$$ to $$$p_{j+1}$$$ for $$$j = 1, 2, \dots, s$$$. The median of a sequence with $$$s$$$ elements is defined as its $$$\left \lceil{\frac{s}{2}} \right \rceil$$$-th smallest element. (For example, the median of $$$[1, 3, 4, 2]$$$ is 2 and the median of $$$[2, 5, 4, 3, 1]$$$ is 3.) The median of a walk is the median of the sequence formed by the weights of its edges.

Input

The first line of input contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 2\times10^5$$$, $$$1 \le k \le 50$$$).

Then $$$m$$$ lines follow. The $$$i^\text{th}$$$ of these lines contains three integers $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$$$).

The graph may contain multiple edges or self-loops.

Output

If no such walks exist, print $$$-1$$$. Otherwise, print one number — the maximum median of a walk with length at least $$$k$$$.

Example
Input
7 7 4
2 1 3
7 2 5
1 7 4
7 5 6
6 4 9
5 2 3
2 3 9
Output
5