#include<iostream>
#include<cstdio>
#include<climits>
#include<queue>
using namespace std;
const int N=100001,M=500001,K=12;
struct E {
	int to,next,val;
}e[K*2*M];
int head[K*N],num;
void add(int f,int to,int v){
	e[++num].to=to;
	e[num].val=v;
	e[num].next=head[f];
	head[f]=num;
}
int n,m,k,s,t;
int dis[K*N];
bool vis[K*N];
inline void dij(int s){//优化后
	for(int i=1;i<=n*(k+1);i++) dis[i]=INT_MAX;
	for(int i=1;i<=n*(k+1);i++) vis[i]=false;
	dis[s]=0;
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int x=q.top().second;q.pop();
		if(vis[x]) continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].next){
			if(vis[e[i].to]) continue;
			if(dis[e[i].to]<=dis[x]+e[i].val) continue;
			dis[e[i].to]=dis[x]+e[i].val;
			q.push(make_pair(-dis[e[i].to],e[i].to));
		}
	}
}
int main() {
	cin>>n>>m>>k;
	cin>>s>>t;
	s++;t++;
	int a,b,c;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		a++;b++;
		add(a,b,c);add(b,a,c);
		for(int j=1;j<=k;j++){
			add(a+j*n,b+j*n,c);
			add(b+j*n,a+j*n,c);
			add(b+(j-1)*n,a+j*n,0);
			add(a+(j-1)*n,b+j*n,0);
		}
	}
	dij(s);
	for(int i=1;i<=k;i++){
		dis[t]=min(dis[t],dis[t+k*n]);
	}
	cout<<dis[t];
	return 0;
}