绿化工程终于完成，整个园区生机勃勃。但是，很不幸的是，在绿化过程中，工人们和进出的车辆将铺设好的电话线全部破坏了。Neyc的领导很生气，问题很严重。为了保住面子，工程队负责人，希望尽快恢复园区的电信，他把这个任务交给了你。已知，园区周围分布n$(1\le n\le 1000)$根按1…n排列的电话线杆，电话线杆之间可以拉电话线。第i对电话线杆的两个端点分别为Ai，Ri，它们间的距离为Li$(1\le li\le 1000000)$。数据中保证每对最多只出现一次。编号为1的电话线杆已经接入了全国的电话网络，整个园区的电话线全部连到了编号为N的电话线杆上。也就是说，你的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。绿化工程的负责人与电信公司协商后，电信公司决定免费为园区连接K$(0\le k\lt n)$对由你指定的电话线杆。对于此外的那些电话线，就必需为它们付费，总费用等于其中最长的电话线长度（每根电话线仅连接一对电话线杆），其它长度不付费。如果需要连接的电话线杆不超过K对，那么总支出为0。现在，你就要设计一个费用最少的方案。最后，计算出将电话线引到园区最少需要花多少钱？
【输入格式】
输入文件的第一行包含三个用空格隔开的整数：N ，P和K。
第二行到第P+1行：每行分别都为三个用空格隔开的整数：Ai Bi和Li。
【输出格式】
输出文件仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出-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