问题 E: E

问题 E: E

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 7
[状态] [讨论版] [提交] [命题人:]
题目描述
在小镇里,有N个凉亭,M条道路,每条路连接两个凉亭。1号凉亭位于人民政府处,N号位于玉龙饭店处。现路面损坏严重,影响交通,且根据路面的损坏程度不同,重新修路的费用不尽相同。现在,镇长决定对路面进行重修,玉龙饭店出于为政府减轻负担的考虑(其实是为了拉生意),大力支持,并采取了以下举措。镇长可以任意指定一条从人民政府通向饭店的路线,指定该路线上不超过P条路,由饭店出钱重修,政府只需要支付路上剩下的修路费用中最高的一个即可。请问政府至少需要支付多少修路的费用,才能将从人民政府到饭店的路修好。(如果路线上一共A条路,而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