#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t;
struct node {
	int v,w;
};
const int MN=1e4*5,MK=11;
bool vis[MN*MK];
int dis[MN*MK];
vector<node> a[MN*MK];
priority_queue<pair<int,int> > dui;
int main(){
	freopen("in1.txt","r",stdin);
	cin>>n>>m>>k>>s>>t;
	int u,v,w,pjr=t;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		int jrt=v;
		for(int j=0;j<=k;j++){
			v=jrt;
			if(j<k){
				a[pjr].push_back((node){pjr+10000,0});
				a[pjr+10000].push_back((node){pjr,0});
			}
			
			for(int x=0;x<=k;x++){
				if(j<x){
					a[u].push_back((node){v,0});
				}
				if(x==j) {
					a[v].push_back((node){u,w});
					a[u].push_back((node){v,w});
				}
				if(j>x){
					a[v].push_back((node){u,0});
				}
				v+=10000;
			}
			pjr+=10000;
			u+=10000;
		}
		
	}
//	cout<<1<<endl;
//	for(int i=0;i<a[10000].size();i++) cout<<a[10000][i].v<<" "<<a[10000][i].w<<"\n";
	memset(dis,0x4f,sizeof(dis));
	dis[s]=0;
	dui.push({0,s});
	while(!dui.empty()){
		u=dui.top().second;
		dui.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<a[u].size();i++){
//			cout<<dis[t]<<"!"<<"\n";
			v=a[u][i].v,w=a[u][i].w;
			if(dis[v]>dis[u]+w&&!vis[v]){
				dis[v]=dis[u]+w;
				dui.push({-dis[v],v});
			}
		}
	}
//	for(int i=0;i<=n-1;i++){
//		cout<<dis[i]<<" ";
//	}
//	cout<<"\n";
	cout<<dis[t]<<"\n";
	fclose(stdin);
	return 0;
}