题目描述
烛龙战队探测到了n个行星，编号从0到n-1。他们当前在编号为s的行星上，需要前往编号为t的行星。这些行星之间有m条轨道，每条轨道连接两个行星。烛龙战队每次行动都必须沿着一条轨道，从一个行星前往另一个行星，走过每条轨道会消耗一定的燃料。同时，在行动过程中，烛龙战队可以开启引力助推装置，借助行星的引力场加速。由于装置的限制，他们最多只能选择k条轨道使用这个装置。在某条轨道使用装置后，走过这条轨道消耗的燃料量就会变成原来的一半。（除以2向下取整）
输入
第一行三个整数 n,m,k，分别表示行星数，轨道数和引力助推次数。（1 ≤ n,m ≤ 10000，1 ≤ k ≤ 10）
接下来一行两个整数 s,t，分别表示起点编号和终点编号。
接下来 m 行，每行三个整数 a,b,c，表示存在一条轨道，能从行星 a 到达行星 b，或从行星 b 到达行星 a，消耗燃料量为 c。（1 ≤ c ≤ 100）
输出
输出一行一个整数，为最少的燃料消耗量。
样例输入
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100样例输出
15