题目描述

在郊区有 $\red {N}$ 座通信基站，$\red {P}$ 条 双向 电缆，第 $\red {i }$条电缆连接基站$\red {A_i}$和$\red {B_i}$ 。

特别地，$\red {1 }$号基站是通信公司的总站，$\red {N}$ 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第$\red { i }$条电缆需要花费$\red {L_i}$ 。

电话公司正在举行优惠活动。

农产主可以指定一条从 $\red {1}$ 号基站到$\red { N}$ 号基站的路径，并指定路径上不超过 $\red {K }$条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第$\red {1}$行：三个整数$\red {N，P，K}$。

第$\red {2..P+1}$行：第 $\red {i+1}$ 行包含三个整数$\red {A _i ,B _i,L _i}$ 。

输出格式

包含一个整数表示最少花费。

若$\red {1}$号基站与$\red {N}$号基站之间不存在路径，则输出$\red {”-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

提示

$\red {0≤K<N≤1000}$,

$\red {1≤P≤10000}$,

$\red {1≤L_i≤1000000}$