#include <bits/stdc++.h> #define scan(x) scanf("%lld", &x) #define scan2(x, y) scanf("%lld%lld", &x, &y) #define scan3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z) #define endl '\n' using namespace std; void scans(string &s) {s.clear();char in=getchar();while(in==' '||in=='\t'||in=='\n'||in=='\r')in=getchar();while(in!=' '&&in!='\n'&&in!='\r'&&in!=EOF)s+=in,in=getchar();} void scanls(string &s) {s.clear();char in=getchar();while(in=='\t'||in=='\r')in=getchar();while(in!='\n'&&in!='\r'&&in!=EOF)s+=in,in=getchar();} using LL = long long; using ll = long long; constexpr LL N = 1e4 + 10; using arr = array <LL, 3>; const LL inf = 0x3f3f3f3f3f3f3f3f; struct Node { LL v, w; }; vector <Node> e[N]; LL n, m, k, s, t, dis[N][15]; bool vis[N][15]; int main() { scan3(n, m, k), scan2(s, t); for(LL i = 1, u, v, w; i <= m; i ++) scan3(u, v, w), e[u].push_back({v, w}), e[v].push_back({u, w}); memset(dis, 0x3f, sizeof dis); *dis[s] = 0; priority_queue <arr, vector <arr>, greater <arr>> pq; pq.push({0, s, 0}); while(pq.size()) { auto nd = pq.top(); pq.pop(); LL d = nd[0], u = nd[1], v = nd[2]; if(vis[u][v]) continue; vis[u][v] = 1; for(auto ed : e[u]) { if(dis[ed.v][v] > d + ed.w) dis[ed.v][v] = d + ed.w, pq.push({dis[ed.v][v], ed.v, v}); if (v < k && dis[ed.v][v + 1] > d) dis[ed.v][v + 1] = d, pq.push({dis[ed.v][v + 1], ed.v, v + 1}); } } LL ans = inf; for(LL j = 0; j <= k; j ++) ans = min(ans, dis[t][j]); printf("%lld\n", ans); return 0; }