#include <bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define xx first
#define yy second
#define inf 0x3f3f3f3f
#define N 10000
#define M 50000
#define K 10
#define gl(x,y) (n*(x)+(y))
using namespace std;
class Edge
{
public:
	int u,v,w,next;
}e[2*M*(4*K+2)+1];
priority_queue<P,vector<P>,greater<P> > r;
bool road[N*K+1];
int elast[N*K+1],dis[N*K+1],n,ans(inf),link;
void add(int u,int v,int w)
{
	e[++link]=(Edge){u,v,w,elast[u]};
	elast[u]=link;
}
void dijkstra(int u)
{
	int v,i;
	memset(dis,inf,sizeof(dis));
	dis[u]=0;
	r.push(make_pair(dis[u],u));
	while(!r.empty())
	{
		u=r.top().yy,r.pop();
		if (road[u]) continue;
		road[u]=true;
		for(i=elast[u];i!=0;i=e[i].next)
		{
			v=e[i].v;
			if (dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				r.push(make_pair(dis[v],v));
			}
		}
	}
}
signed main()
{
	//[JLOI2011]飞行路线（【模板】分层图操作）
	int m,k,s,t,a,b,c,i;
	scanf("%lld%lld%lld%lld%lld",&n,&m,&k,&s,&t);
	s++,t++;
	while(m--)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		a++,b++;
		add(a,b,c),add(b,a,c);
		for(i=1;i<=k;i++)
		{
			add(gl(i-1,a),gl(i,b),0);
			add(gl(i-1,b),gl(i,a),0);
			add(gl(i,a),gl(i,b),c);
			add(gl(i,b),gl(i,a),c);
		}
	}
//	for(i=1;i<=k;i++) add(gl(i-1,t),gl(i,t),0);
	dijkstra(s);
	for(i=0;i<=k;i++) ans=min(ans,dis[gl(i,t)]);
	printf("%lld",ans);
}