航空公司一共在n个城市设有业务，这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对这次旅行也推出优惠，可以免费乘坐k次飞机（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(0 \le a_i, b_i \lt n), w_i(1 \le w_i \le 10^3) ，表示城市 a_i 和 b_i 之间有一条航线，价格为 w_i 。
输入保证s,t之间可达。

最少的花费。