3303: 修建道路
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：2
题目描述
sub打算修建一条磁悬浮列车的通道连接现代OI王国的首都(编号为1)和sub的家(编号为n)。当然，现代OI集团的n(1<=n<=1000)座城市之间没有任何的磁悬浮通道，而sub通过实地勘测发现，一共有p(1<=P<=10000)对城市之间可以建磁悬浮通道。在这p对城市之中，第i对城市分别为ai,bi，它们间的距离为li(1<=li<=1000000)。数据中保证每对{ai,bi}最多只出现1次，现代OI集团决定免费帮sub修建最多k条线路的磁悬浮通道，而sub要花的钱，是他自己负责修建的那些线路的最长的那条路的长度。sub当然想花最少的钱......他想知道他最少能花多少钱。
输入
第1行:3个用空格隔开的整数:n,p,以及k第2..p+1行:第i+1行为3个用空格隔开的整数:ai,bi,li
输出
输出1个整数,为sub在这项工程上的最小支出.如果任务不可能完成,输出-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提示
【样例说明】现代OI集团一共有5个城市。城市1不能直接与城市4,5相连。城市5不能直接与城市1,3相连。其余所有城市间均可修建轨道。现代OI集团可以免费为sub修建一条线路。
sub选择如下的修建方案:1->3,3->2,2->5，这3条路线的长度分别为4,3,9。sub让现代OI集团免费修建那条长度为9的路线，于是，他所需要花费的钱为4。