时间限制：1秒　　内存限制：256M

---

【题目描述】

　　北极地区共有 \(n\) 座村庄，按1..n编号。现在决定在村庄之间建立通信网络，一共有 \(m\) 对村庄之间可以直接连接通讯电缆，其余的那些由于隔得太远而无法被连接。第 i 对电话线杆的两个端点分别为 \(a_i、b_i\)，它们间的距离为 \(d_i\)。数据中保证每对 \((a_i，b_i)\) 最多只出现 1 次。编号为 1 的村庄已经接入了卫星网络。

由于暴雪天气，现在最紧迫的任务是要尽快建立一条将 1 号村庄和 \(n\) 号村转连起来的通信线路，其余的村庄连入通信网络没有那么急迫。

　　经过谈判，环球电信公司最终同意免费为连结 \(p\) 对地区通信电缆。对于此外的那些电缆，政府需要付费，等于其中最长的电缆的长度。当然，如果需要连结的村庄不超过 \(p\) 对，那么政府的总支出就为 0。

　　请你计算一下，政府最少需要在电缆上花多少钱？

【输入格式】

　　第 1 行: 3 个用空格隔开的整数：\(n，m\) 以及 \(p\)。
　　第 \(2..m+1\) 行: 第 \(i+1\) 行为三个用空格隔开的整数：\(a_i，b_i，d_i\)。

【输出格式】

　　输出一行一个整数，为最小的花费。如果任务不可能完成，则输出 -1。

【输入输出样例】

　Input

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

　Output

4

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤1000\)，\(1≤m≤10000\)，\(1≤p≤30\)，\(1≤d_i≤1000000\)

【来源】

　　Mr.he