题目描述
sub打算修建一条磁悬浮列车的通道连接现代OI王国的首都(编号为 $1$ )和sub的家(编号为 $n$ )。
当然，现代OI集团的 $n$ 座城市之间没有任何的磁悬浮通道，而sub通过实地勘测发现，一共有 $p$ 对城市之间可以建磁悬浮通道。
在这 $p$ 对城市之中，第 $i$ 对城市分别为 $a_i,b_i$，它们间的距离为 $l_i$ 。数据中保证每对 $(a_i,b_i)$ 最多只出现 $1$ 次，
现代OI集团决定免费帮sub修建最多 $k$ 条线路的磁悬浮通道，而sub要花的钱，是他自己负责修建的那些线路的最长的那条路的长度。
sub当然想花最少的钱，他想知道他最少能花多少钱。
输入
第 $1$ 行输入 $3$ 整数，$n,p,k$ 。
第 $2$ 行到第 $p+1$ 行，其中第 $i+1$ 行为 $3$ 个用空格隔开的整数，$a_i,b_i,l_i$ 。
输出
输出 $1$ 个整数,为sub在这项工程上的最小支出.如果任务不可能完成,输出 `-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
提示
【样例解释】
现代OI集团一共有 $5$ 个城市。城市 $1$ 不能直接与城市 $4,5$ 相连。城市 $5$ 不能直接与城市 $1,3$ 相连。其余所有城市间均可修建轨道。现代OI集团可以免费为sub修建一条线路。
sub选择如下的修建方案: $1 \to 3,3 \to 2,2\to 5$，这 $3$ 条路线的长度分别为 $4,3,9$ 。sub让现代OI集团免费修建那条长度为 $9$ 的路线，于是，他所需要花费的钱为 $4$ 。
对于 $100\%$ 的数据，满足 $1 \leq k \leq n \leq 10^3$，$1 \leq p \leq 10^4$，$1 \leq l_i \leq 10^6$。