#include<bits/stdc++.h> using namespace std; const int K=13,N=1e4+2; int n,m,k,s,t; struct edge { int d,v,w; }; vectorg[K][N]; bool vis[K][N]; int dis[K][N]; #define pii pair<int,pair<int,int>> priority_queue<pii,vector,greater>q;

void dijkstra() { memset(dis,0x3f,sizeof dis); dis[1][s]=0; q.push({0,{1,s}}); while(!q.empty()) { int d=q.top().second.first,u=q.top().second.second; q.pop(); if(vis[d][u])continue; vis[d][u]=1; for(auto v_:g[d][u]) { int vd=v_.d,v=v_.v,w=v_.w; if(dis[d][u]+w<dis[vd][v]) { dis[vd][v]=dis[d][u]+w; q.push({dis[vd][v],{vd,v}}); } } } } #if 0 _ _ -> | | | | -> | | | | | | | | | | | |
|| ||

#endif

#undef pii signed main() { cin>>n>>m>>k>>s>>t; for(int i=1,a,b,c;i<=m;i++) { cin>>a>>b>>c; for(int j=1;j<=k+1;j++) { g[j][a].push_back({j,b,c}); g[j][b].push_back({j,a,c}); } } for(int i=1;i<=k+1;i++) for(int j=0;j<n;j++) for(auto v:g[i][j]) g[i][j].push_back({i+1,v.v,0}); dijkstra(); int mi=2e9; for(int i=1;i<=k+1;i++) mi=min(mi,dis[i][t]); cout<<mi; return 0; }