本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-02 15:39:23

因为数据范围很小，一开始的思路是对每一个经过的无权边数量的方案都求一个最短路，如经过1条无权边的最短路，两条的最短路。。。

这里并不需要使经过的无权边不重复，因为我只关心这里面经过最短路小于等于L同时无权边最少的方案。容易发现这个方案一定不会有无权边被重复经过。

复杂度是 $\mathrm{O(n^2\log m)}$ ，如果每一条边都是无权边的话可能会过不去，但没有这样的数据。结果跑过了，，

然而题解区有一个更好的 $\mathrm{O(n\log m\log(mL))}$ 的方法。

发现同时给所有无权边加1，若存在答案且当前最短路小于 $L$ ，则最短路长度一定至少增加1。

然后只给其中一条边加1，最短路长度最多增加1。

直接给每一个无权边定一个序号，然后二分即可。需要判一下没有无权边和达不到L的情况。

code

struct edge{
	int v,w,nxt;
}e[M<<1];
int head[N],tott;
void add(int u,int v,int w){e[++tott]={v,w,head[u]},head[u]=tott;}

struct Edge{
	int u,v,w;
}E[M];

vector<int>eg;

int st,ed;

struct hhh{
	int u,w;
	bool operator<(hhh ano)const{
		return w>ano.w;
	}
};
priority_queue<hhh>q;

int dis[N];
bool vis[N];

int dij(){
	q.push({st,0});
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[st]=0;
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[u]+w<dis[v])
				dis[v]=dis[u]+w,q.push({v,dis[v]});
		}
	}
	return dis[ed];
}

int check(int x){
	int tmp=x%eg.size();
	for(int i:eg){
		if(tmp==0)
			e[2*i-1].w=e[2*i].w=x\/eg.size();
		else
			e[2*i-1].w=e[2*i].w=x\/eg.size()+1,tmp--;
	}
	return dij();
}

signed main(){
	int n=read(),m=read(),L=read();st=read(),ed=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		if(w==0)
			eg.pb(i);
		add(u,v,w);add(v,u,w);
		E[i]={u,v,w};
	}
	if(eg.size()==0){
		if(dij()==L){
			printf("YES\n");
			for(int i=1;i<=m;i++)
				print(E[i].u),pc(' '),print(E[i].v),pc(' '),print(E[i].w),pc('\n');
		}else
			printf("NO\n");
		return 0;
	}
	int l=eg.size(),r=(__int128)(eg.size())*1e9,ans=-1;
	while(l<=r){
		int tmp=check(mid);
		if(tmp<=L){
			if(tmp==L)
				ans=mid;
			l=mid+1;
		}else
			r=mid-1;
	}
	if(ans==-1)
		printf("NO\n");
	else{
		int tmp=ans%eg.size();
		for(int i:eg){
			if(tmp==0)
				E[i].w=ans\/eg.size();
			else
				E[i].w=ans\/eg.size()+1,tmp--;
		}
		printf("YES\n");
		for(int i=1;i<=m;i++)
			print(E[i].u),pc(' '),print(E[i].v),pc(' '),print(E[i].w),pc('\n');
	}
	return 0;
}