背景

^_^

题目描述

某国共有n座城市，有m条高速公路连接这些城市，每条高速公路只能单向通行。

第i条高速公路的起点城市是$u_i$ ，终点城市是$v_i$ ，经过一次需要$w_i$的费用。

节假日到了，国家决定对高速公路通行费进行减免，政策如下：

如果一条路线经过的高速公路不超过k条，将按照原价收取费用。

如果一条路线经过的高速公路超过k条，将只收取其中费用最高的k条高速公路的费用。

求：从城市s到城市t的最小花费。

格式

输入

第1行，5个正整数n,m,k,s,t。

接下来m行，每行3个正整数$u_i$ ,$v_i$ ,$w_i$ ，表示一条高速公路。

保证从s出发一定能到达t。

输出

一个数，x 和 y 的和。

样例

6 6 2 1 6
1 2 5
2 3 4
3 6 3
1 4 5
4 5 5
5 6 1

9

样例解释

费用最小的路线为1->2->3->6，其中费用最高的两条高速公路分别为5和4，总费用为9。

测试限制

对于20%的数据，n,k<=15，m<=25。

对于40%的数据，n,k<=50，m<=100。

对于70%的数据，n,k<=200，m<=300。

对于100%的数据，n,k<=1000，m<=2000，$s,t,u_i,v_i <=n，s!=t，u_i !=v_i ，w _i <=10^9$。

保证至少存在一种从s到t的方案。

保证不存在两条高速公路i,j满足$u_i=u_j且v_i=v_j$ 。

每个测试点均为 2s, 内存总限制512MB .