题目描述
在小镇里，有N个凉亭，M条道路，每条路连接两个凉亭。1号凉亭位于人民政府处，N号位于玉龙饭店处。现路面损坏严重，影响交通，且根据路面的损坏程度不同，重新修路的费用不尽相同。现在，镇长决定对路面进行重修，玉龙饭店出于为政府减轻负担的考虑（其实是为了拉生意），大力支持，并采取了以下举措。镇长可以任意指定一条从人民政府通向饭店的路线，指定该路线上不超过P条路，由饭店出钱重修，政府只需要支付路上剩下的修路费用中最高的一个即可。请问政府至少需要支付多少修路的费用，才能将从人民政府到饭店的路修好。（如果路线上一共A
条路，而P>=A，那么相当于免费，即费用为0）
条路，而P>=A，那么相当于免费，即费用为0）
输入
第一行三个数N M P (1
<= N <= 1000, 1 <= M <= 10000, 0 <= P <= M)
接下来M行，每行三个数A B C表示凉亭A到B之间有一条道路，重新修路的费用为C。
输出
在饭店的资助下，重新修好从人民政府到饭店的路政府至少需要支付的费用。
样例输入
Copy
4 3 1
1 2 3
1 3 4
3 4 3
样例输出 Copy
3
提示
若人民政府到饭店之间不存在路径，输出-1