该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

无向图有 $N$ 个点，$M$ 条双向边，第 $i$ 条边连接点 $A_i$ 和点 $B_i$ ,边的权值为 $L_i$ 。

找出一条点 $1$ 至 点 $N$ 的路径，使得该路径中的边权最大值最小。

特殊技能：确定某条路径后，最多允许该路径中有 $K$ 条边不计边权。

【输入格式】

第一行三个整数 $N，M，K$（$0 \le K < N \le 10^3,1 \le M \le 10^4$ ）

下来 $M$ ，每行包含三个整数 $A_i,B_i,L_i$（$1 \le A_i,B_i \le 10^6, 1 \le L_i \le 10^6$）。

【输出格式】

一行一个整数，表示点 $1$ 至点 $N$ 的路径中的最大边权的最小值。 若不存在路径，则输出 -1。

【输入样例】

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

【输出样例】

4