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

题目描述

怪盗基德在沙漠寻宝，在这个沙漠中，有N个位置和P条 双向 的公路，第i条公路连接宝箱$A_i$和$B_i$。 基德目前在1号宝箱面前，他一定要到达n号宝箱那里。现在，基德想要对这些公路进行升级操作，其中第i条公路升级需要花费$L_i$。 然后，基德和奇异博士学会了一个魔法，可以指定一条从1号位置到n号位置的路径，并指定不超过K条公路免费升级。 基德只需要从剩余到道路中，升级价格 最贵 的公路，即可完成本次升级，问至少花费多少钱才能完成升级？

输入格式

第1行：三个整数N，P，K。 第2..P+1行：第 i+1 行包含三个整数$A_i,B_i,L_i$。 包含一个整数表示最少花费。 若1号位置与N号位置之间不存在路径，则输出”-1”。

输出格式

一个数，即答案

样例 #1

样例输入 #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

样例输出 #1

4

提示

数据范围：0≤K<N≤1000,1≤P≤2000