架设电话线

题目描述:

一共有N个电线杆，有P对电线杆是可以连接的，用几条线连接在一起的电线杆之间都可相互通信，现在想要使得电线杆1和电线杆N能相互通信，并且电线公司提出K条电线是可以免费使用的，当使用电线的数量超过K条，超出的电线要收费，收的总费用为去掉免费使用的K条电线之后最长的那条电线的长度。

现在需要尽可能的减少费用，问最少费用是多少

输入格式:

第一行三个整数N, P, K。

接下来P行，每行三个整数Ai, Bi, Li。

输出格式:

若不存在从1到N的线路，输出“-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

提示:

0 ≤ K < N≤ 1000, 1≤P ≤ 10,000。

简单地说，本题是在无向图上求出一条从1到N的线路，使线上第K+1条大的边权尽量小。

时间限制: 1000ms
空间限制: 256MB

---