用了一种清奇的思路（不是分层图）去做，希望能被Hack。

#include<bits/stdc++.h>
#define eps 1e-5
using namespace std;
namespace io {
	inline int read() {
		int __x=0,__f=1;
		char __c=getchar();
		while(__c<'0'||__c>'9') {
			if(__c=='-')__f=-1;
			__c=getchar();
		}
		while(__c>='0'&&__c<='9') {
			__x=__x*10+__c-'0';
			__c=getchar();
		}
		return __x*__f;
	}
}
using namespace io;
const int maxn=5e4+5,maxm=2e5+5;
struct que {
	int id;
	double x;
	friend bool operator<(que a,que b) {
		return a.x>b.x;
	}
};
struct edge {
	int next,to;
	double v;
} e[maxm],w[maxm];
int h[maxn],g[maxn],cnt,cnt2,d1[maxn],n,m,k,vst[maxn],S,E;
double d[maxn],ans;
priority_queue<que> q;
inline void addedge(int x,int y,int z) {
	e[++cnt].next=h[x];
	e[cnt].to=y;
	e[cnt].v=z;
	h[x]=cnt;
}
inline void addedge2(int x,int y) {
	w[++cnt2].next=g[x];
	w[cnt2].to=y;
	g[x]=cnt2;
}
inline double dijkstra(double mid) {
	for(register int i=1; i<=n; i++) {
		d[i]=1e9;
	}
	memset(d1,0,sizeof(d1));
	memset(vst,0,sizeof(vst));
	d[S]=0;
	q.push((que) {
		S,0
	});
	while(!q.empty()) {
		int u=q.top().id;
		q.pop();
		if(vst[u])continue;
		vst[u]=1;
		for(register int i=h[u]; i; i=e[i].next) {
			int j=e[i].to;
			if(d[j]>d[u]+e[i].v||(d[j]==d[u]+e[i].v&&d1[j]>d1[u])) {
				d[j]=d[u]+e[i].v;
				d1[j]=d1[u];
				if(!vst[j]) {
					q.push((que) {
						j,d[j]
					});
				}
			}
		}
		for(register int i=g[u]; i; i=w[i].next) {
			int j=w[i].to;
			if(d[j]>d[u]+mid||(d[j]==d[u]+mid&&d1[j]>d1[u]+1)) {
				d[j]=d[u]+mid;
				d1[j]=d1[u]+1;
				if(!vst[j]) {
					q.push((que) {
						j,d[j]
					});
				}
			}
		}
	}
	if(d1[E]>k)return -1;
	return d[E]-d1[E]*mid;
}
signed main() {
	int x,y,z;
	n=read()+1,m=read(),k=read();
	S=read()+1,E=read()+1;
	for(register int i=1; i<=m; i++) {
		x=read()+1,y=read()+1,z=read();
		addedge(x,y,z);
		addedge(y,x,z);
		addedge2(x,y);
		addedge2(y,x);
	}
	double l=-1e5,r=1e5;
	while(r-l>eps) {
		double mid=(l+r)/2;
		int p=dijkstra(mid);
		if(p==-1) {
			l=mid;
		} else {
			r=mid;
			ans=p;
		}
	}
	printf("%.0lf",ans);
	return 0;
}