代码:

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N=600005,M=6000005;
int h[N],e[M],w[M],ne[M],d[N],idx,n,m,k,v[N];
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> >que;
void add(int x,int y,int z) {
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}
void Dijkstra(int sx) {
	memset(d,0x7f,sizeof d);
	d[sx]=0;
	que.push({0,sx});
	while (!que.empty()) {
		PII t=que.top();
		que.pop();
		int x=t.second;
		if (v[x]==1) continue;
		v[x]=1;
		for (int i=h[x];i!=-1;i=ne[i]) {
			int j=e[i];
			if (d[j]>d[x]+w[i]) {
				d[j]=d[x]+w[i];
				que.push({d[j],j});
			}
		}
	}
}
int main() {
	memset(h,-1,sizeof h);
	scanf("%d %d %d",&n,&m,&k);
	int sx,ex;
	scanf("%d %d",&sx,&ex);
	sx++,ex++;
	while (m--) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		x++,y++;
		for (int i=0;i<=k;i++) {
			add(x+i*n,y+i*n,z);
			add(y+i*n,x+i*n,z);
			if (i==k) break;
			add(x+i*n,y+(i+1)*n,0);
			add(y+i*n,x+(i+1)*n,0);
		}
	}
	Dijkstra(sx);
	int ans=0x7f7f7f7f;
	for (int i=0;i<=k;i++) {
		ans=min(ans,d[(i+1)*ex]);
	}
	printf("%d",ans);
	return 0;
}