2763. [JLOI2011]飞行路线

题目描述

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

输入格式

数据的第一行有三个整数，$n,m,k$，分别表示城市数，航线数和免费乘坐次数。

第二行有两个整数，$s,t$，分别表示他们出行的起点城市编号和终点城市编号。$(0<=s,t<n)$

接下来有$m$行，每行三个整数，$a,b,c$，表示存在一种航线，能从城市$a$到达城市$b$，或从城市$b$到达城市$a$，价格为$c$。$(0<=a,b<n$,$a$与$b$不相等，$0<=c<=1000)$

输出格式

只有一行，包含一个整数，为最少花费。

样例

样例输入

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

样例输出

8

数据范围与提示

对于$30$%的数据,$2<=n<=50,1<=m<=300,k=0;$

对于$50$%的数据,$2<=n<=600,1<=m<=6000,0<=k<=1;$

对于$100$%的数据,$2<=n<=10000,1<=m<=50000,0<=k<=10.$