Find the Path

Given an undirected weighted graph with nodes numbered 1..N and M edges. Among all paths from node 1 to node N that use at most K edges, find the one whose "maximum edge weight on the path" is smallest, and output that minimum maximum edge weight. At least one such path is guaranteed to exist.

输入格式

The first line contains three integers N, M, K. Each of the next M lines contains three integers u, v, w, meaning an undirected edge of weight w between u and v (parallel edges are possible, but there are no self-loops). 2≤N≤100000, 1≤M≤200000, 1≤K≤N−1, 1≤w≤10^9.

输出格式

Output one integer: the minimum maximum edge weight.

样例 1

输入：

4 4 3
1 2 4
1 3 2
2 4 5
2 3 6

输出：

5

样例 2

输入：

4 5 2
1 2 1
2 3 1
3 4 1
1 3 8
3 4 2

输出：

8

样例 3

输入：

2 2 1
1 2 7
1 2 3

输出：

3

样例说明

Example 1: N=4, K=3. The path 1→2→4 has maximum edge weight 5; the path 1→3→2→4 has maximum edge weight 6. The answer is 5. Example 2: with K=2, you cannot take 1→2→3→4 (3 edges), only 1→3→4, whose maximum edge weight is 8. Example 3: there are two edges between 1 and 2; choose the one with weight 3.