rt，

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define P pair<int,int>
#define pf first
#define ps second
using namespace std;
class Edge
{
public:
	int u,v,w,next;
}e[2200002];
priority_queue<P,vector<P>,greater<P> > r;
bool road[110002];
int elast[110002],dis[110002],n,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().ps,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));
			}
		}
	}
}
int main()
{
	//[JLOI2011]飞行路线
	int m,k,s,t,a,b,c,i;
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	s++,t++;
	while(m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		a++,b++;
		add(a,b,c),add(b,a,c);
		for(i=1;i<=k;i++)
		{
			add(a+(i-1)*n,b+i*n,0),add(b+(i-1)*n,a+i*n,0);
			add(a+i*n,b+i*n,c),add(b*i*n,a+i*n,c);
		}
	}
	for(i=1;i<=k;i++) add(t+(i-1)*n,t+i*n,0);
	dijkstra(s);
	printf("%d",dis[t+k*n]);
}