structnode{ int v, w, next; }edge[5000005]; constint inf = 0x3f3f3f3f; constint maxn = 5e6 + 10000; int tot = 0, head[maxn], vis[maxn], dist[maxn]; voidadd(int u, int v, int w) { edge[++tot].v = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot; } priority_queue<pair<int,int> >Q; voiddijkstra(int S) { Q.push({-0, S}); dist[S] = 0; while(!Q.empty()) { int u = Q.top().second; Q.pop(); if(vis[u])continue; vis[u] = 1; for(int k = head[u]; k != -1; k = edge[k].next) { int v = edge[k].v; int w = edge[k].w; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; Q.push({-dist[v], v}); }
} } } constint N = 1000; intmain() { int n, m, S, T, k,u, v, w; cin >> n >> m >> S >> T >> k; memset(dist, inf, sizeof(dist)); memset(head, -1, sizeof(head)); for(int i = 1; i <= m; ++i) { scanf("%d%d%d",&u,&v,&w); add(u, v, w); add(v, u, w); for(int j = 1; j <= k; ++j) { add(u + (j-1) * N,v + j * N, 0); add(v + (j-1) * N , u + j * N, 0); add(u + j * N , v + j * N, w); add(v + j * N, u + j * N, w); } } dijkstra(S); int Min = inf; for(int i = 0; i <= k; ++i) { Min = min(Min, dist[T + i * N]); } cout << Min <<'\n'; return0; }