37pts
WA

#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,w;
};

struct pit{
	int x,kk,dis;
	bool operator <(const pit &A)const{
		return A.dis<dis;
	}
};

int n,m,k;
int u,v,w;
int s,t;
int ans=1e9;
vector<node>edg[10003];
int dis[10003][13];
bool vis[10003][13];

priority_queue<pit>q;

inline void dijkstra(int s){
	dis[s][0]=0;
	q.push((pit){s,0,0});
	while(!q.empty()){
		int x=q.top().x,kk=q.top().kk;
		q.pop();
		if(vis[x][kk])break;
		vis[x][kk]=1;
		for(int i=0;i<edg[x].size();i++){
			int to=edg[x][i].to,w=edg[x][i].w;
			if(dis[to][kk]>dis[x][kk]+w){
				dis[to][kk]=dis[x][kk]+w;
				q.push((pit){to,kk,dis[to][kk]});
			}
			if(kk<k&&dis[to][kk+1]>dis[x][kk]){
				dis[to][kk+1]=dis[x][kk];
				q.push((pit){to,kk+1,dis[to][kk+1]});
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	cin>>s>>t;
	for(int i=0;i<n;i++){
		for(int j=0;j<=k;j++){
			dis[i][j]=1e9;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		edg[u].push_back((node){v,w});
		edg[v].push_back((node){u,w});
	}
	dijkstra(s);
	for(int i=0;i<=k;i++){
		ans=min(ans,dis[t][i]);
	}
	cout<<ans;
	return 0;
}