4460 - 第十课:飞行路线

航空公司一共在n个城市设有业务,这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对这次旅行也推出优惠,可以免费在最多k种航线上搭乘飞机。那么这次出行最少花费多少?

输入

第一行输入三个整数$ n(2 \le n \le 10^4), m(0 \le m \le 5*10^4), k(0 \le k \le 10) $。
第二行有两个整数$ s, t(0 \le s, t \lt n) $。
接下来m行,每行输入三个整数$ a_i, b_i(1 \le a_i, b_i \le n), w_i(1 \le w_i \le 10^3) $,表示城市$ a_i $和$ b_i $之间有一条航线,价格为$ w_i $。
输入保证s,t之间可达。
 

输出

最少的花费。

样例

输入

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100

输出

8
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题