//分层图:对同一个边有不同种操作,我们采用分层图,第一种操作在第一层,第二种操作在第二层,以此类推
//如果当前跳到了第二层,那么下一次转移也要在那一层或者是下一层进行
//dist[i][j]表示到达i号结点,用了j次机会的路径
#include<iostream>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
const int N = 1e4 + 10,M = 2e5 + 10,INF = 0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
int dist[N][15];
bool st[N][15];
int n,m,k,sa,ed;
struct Node
{
int ver,d,p;//当前的点,距离起点的距离,已经用过几次免费机会了
bool operator <(const Node &t)const
{
return d > t.d;
}
};
void add(int a,int b,int c)
{
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}
void dijkstra()
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
priority_queue<Node>q;
dist[sa][0] = 0;
q.push({sa, 0, 0});
while(!q.empty())
{
auto t = q.top();
q.pop();
int ver = t.ver,distance = t.d,p = t.p;
if(st[ver][p])continue;
st[ver][p] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
//用免票机会的情况
if(p < k)
{
if(dist[j][p + 1] > distance)
{
dist[j][p + 1] = distance;
q.push({j, dist[j][p + 1], p + 1});
}
}
//不用的情况
if(dist[j][p] > distance + w[i])
{
dist[j][p] = distance + w[i];
q.push({j, dist[j][p], p});
}
}
}
}
int main()
{
cin >> n >> m >> k >> sa >> ed;
memset(h, -1, sizeof h);
sa ++,ed ++;
while(m --)
{
int a,b,c; cin >> a >> b >> c;
add(a + 1,b + 1,c),add(b + 1,a + 1,c);
}
dijkstra();
//有可能我们走不到最深层的终点,所以要对所有的k取最小
//比如说我们只需要一条边就能到终点,但是有多余1张的机票
int res = INF;
for(int j = 0; j <= k; j ++)
res = min(res, dist[ed][j]);
cout << res << endl;
// cout << dist[ed][k] << endl;
return 0;
}