题目描述

Farmer John想在他的农场安装电话线。不幸的是，电话公司不太配合，所以他需要为连接农场到电话系统所需的部分电缆付费。

农场周围散布着N根（1 ≤ N ≤ 1000）编号为1..N的废弃电话线杆，目前没有任何电缆连接它们。共有P（1 ≤ P ≤ 10000）对电线杆可以通过电缆连接，其余的因距离太远而无法连接。

第i条电缆可以连接两根不同的电线杆Ai和Bi，若使用该电缆，其长度为Li（1 ≤ Li ≤ 10^6）单位。输入数据中，每对{Ai, Bi}最多出现一次。电线杆1已经连接到电话系统，电线杆N位于农场。需要通过电缆路径将电线杆1和N连接起来，其余电线杆可以选择使用或不使用。

实际上，电话公司愿意免费为Farmer John提供K段电缆。除此之外，他需要支付的费用等于所需剩余电缆中最长的那一段的长度（每对电线杆之间用单独的电缆连接）；如果不需要额外电缆，则费用为0。

请计算Farmer John必须支付的最小费用。若无法连接农场和电话系统，输出-1。

输入格式

• 第1行：三个空格分隔的整数N、P、K
• 第2..P+1行：第i+1行包含三个空格分隔的整数Ai、Bi、Li

输出格式

• 第1行：一个整数，表示Farmer John能支付的最小费用。若无法连接，输出-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  

来源

USACO 2008年1月银牌题

解题思路提示

该问题可转化为在图中寻找从1到N的路径，使得路径中第K+1长的边的长度最小。可通过枚举可能的边长阈值，结合并查集判断是否存在满足条件的路径，或使用基于边权排序的最小生成树变种算法求解。