#include <bits/stdc++.h>
using namespace std;

const int N = 4000010;
int h[N],e[N],w[N],ne[N],idx=0;
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int n,m,k;
int dist[N];
struct node
{
	int step,u;
	bool operator < (const node&cmp) const
	{
		return step>cmp.step;
	}
};
int s,t;
priority_queue<node> q;
bool flag[N];
void dijkstra()
{
	q.push({0,s});
	memset(dist,0x3f,sizeof dist);
	dist[s]=0;
	
	while(!q.empty())
	{
		node f=q.top();
		q.pop();
		
		if(flag[f.u]) continue;
		flag[f.u]=1;
		for(int i=h[f.u];i!=-1;i=ne[i])
		{
			if(!flag[e[i]] && dist[f.u]+w[i]<dist[e[i]])
			{
				dist[e[i]]=dist[f.u]+w[i];
				q.push({dist[e[i]],e[i]});
			}
		}
	}
	printf("%d",dist[t+n*k]);
}
int main()
{
	memset(h,-1,sizeof h);
	scanf("%d%d%d",&n,&m,&k);
	scanf("%d%d",&s,&t);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
		for(int j=1;j<=k;j++) add(a+n*(j-1),b+n*j,0),add(b+n*j,a+n*(j-1),0),add(a+n*j,b+n*j,c),add(b+n*j,a+n*j,c);
	}
	for(int i=1;i<=k;++i)
	{
		add(t+(i-1)*n,t+i*n,0);
	}
	dijkstra();
}

https://www.luogu.com.cn/problem/P4568