Description

John is building a new milking machine, but he does not want others to know. He wants to keep this secret for as long as possible. He hides the machine somewhere on his farm so it will not be found.

During the manufacturing process, he needs to go to the machine’s location $T$ times. His farm has secret tunnels, but John uses them only on the return trip. The farm is divided into $N$ regions, labeled from $1$ to $N$. These regions are connected by $P$ roads, each road has a length $L$ less than $10^6$. There may be multiple roads between two regions. To reduce the chance of being discovered, John will not traverse any road on the farm more than once. Of course, he wants the routes to be as short as possible.

Please help John find $T$ routes from the warehouse to the milking machine’s location. The warehouse is region $1$, and the milking machine is at region $N$. We ask for the minimal possible value of the length of the longest road among all the roads John will traverse, subject to the condition that no road is reused.

Note that we are not minimizing the total route length. We are minimizing the maximum length among the roads that directly connect two regions (i.e., edges). The testdata guarantees that John can find $T$ routes from the warehouse to region $N$ without reusing any road.

Input Format

The first line contains $3$ integers $N$, $P$, and $T$, separated by spaces.

Lines $2$ to $P+1$: each line contains $3$ integers $A_i$, $B_i$, and $L_i$, indicating there is a road between regions $A_i$ and $B_i$ with length $L_i$.

Output Format

Output a single line containing one integer: the minimal possible value of the longest road’s length among those John traverses.

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

5

Hint

Choose routes $1-2-3-7$ and $1-6-7$. The minimal possible value of the longest road among these routes is $5$.

For $100\%$ of the testdata: $2 \le N \le 200$, $1 \le P \le 4 \times 10^4$, $1 \le T \le 200$, and each road length $\le 10^6$.

Translated by ChatGPT 5