很好发现,去掉边 $i$ 最短路发生改变当且仅当边 $i$ 一定在每条最短路上。定义从点 $1$ 到 $i$ 的最短路距离为 $dis1_i$，从点 $n$ 到 $i$ 的最短路距离为 $dis2_i$，从点 $1$ 到 $i$ 的最短路方案数为 $posi1_i$，从点 $n$ 到 $i$ 的最短路方案数为 $posi2_i$。那么一条从 $u$ 到 $v$ 长度为 $z$ 边一定在最短路上当且仅当满足以下条件中的一个：

• $dis1_u+dis2_v+z=dis1_n$ 且 $posi1_u \times posi2_v=posi1_n$
• $dis1_v+dis2_u+z=dis1_n$ 且 $posi1_v \times posi2_u=posi1_n$

上面这些信息很好处理，唯一需要注意的就是对于任意一点 $u$，方案数可能会溢出。只需要把它们对 $998244353$ 取模即可。

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int mod=998244353;
long long n,m,st,ed,idx,x,y,z;
int elast[200010];
int dis[200010],posi[200010],dis2[200010],posi2[200010];
struct edge{int x,y,z,pre;}a[400010];
void merge(int x,int y,int z)
{
	a[++idx]={x,y,z,elast[x]};
	elast[x]=idx;
}
struct node{int u,dis;};
bool operator < (node x,node y){return x.dis>y.dis;} 
priority_queue<node>q;
bool vis[200010];
void dijkstra()//从 1 开始跑最短路
{
	q.push({st,0});
	while(!q.empty())
	{
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=elast[u];i;i=a[i].pre)
		{
			if(dis[a[i].y]>=dis[u]+a[i].z)
			{
				if(dis[a[i].y]==dis[u]+a[i].z)posi[a[i].y]=(posi[a[i].y]+posi[u])%mod;//距离相等则方案数累加
				else
				{
					posi[a[i].y]=posi[u];//距离更短则方案数为先前结点的方案数
					dis[a[i].y]=dis[u]+a[i].z;
					q.push({a[i].y,dis[a[i].y]});
				}
			}
			
		}
	}
}
void dijkstra2()//从 n 开始跑最短路，与前面大致相同
{
	q.push({ed,0});
	while(!q.empty())
	{
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=elast[u];i;i=a[i].pre)
		{
			if(dis2[a[i].y]>=dis2[u]+a[i].z)
			{
				if(dis2[a[i].y]==dis2[u]+a[i].z)posi2[a[i].y]=(posi2[a[i].y]+posi2[u])%mod;
				else 
				{
					posi2[a[i].y]=posi2[u];
					dis2[a[i].y]=dis2[u]+a[i].z;
					q.push({a[i].y,dis2[a[i].y]});
				}
			}
			
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(dis,0x7f,sizeof dis);
	memset(dis2,0x7f,sizeof dis2);
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		merge(x,y,z),merge(y,x,z);
	}
	st=1,ed=n;
	dis[st]=0;
	posi[st]=1;
	dijkstra();
	memset(vis,0,sizeof vis);
	dis2[ed]=0;
	posi2[ed]=1;
	dijkstra2();
	for(int i=1;i<=idx;i+=2)
	{
		if(dis[a[i].x]+dis2[a[i].y]+a[i].z!=dis[ed]&&dis[a[i].y]+dis2[a[i].x]+a[i].z!=dis[ed])cout<<"No\n";//距离不相等
		else
		{
			if(((dis[a[i].x]+dis2[a[i].y]+a[i].z==dis[ed])&&(posi[a[i].x]*posi2[a[i].y]%mod==posi[ed]))||((dis[a[i].y]+dis2[a[i].x]+a[i].z==dis[ed])&&(posi[a[i].y]*posi2[a[i].x])%mod==posi[ed]))cout<<"Yes\n";
			else cout<<"No\n";
		}
	}
	return 0;
}