AC 26 WA 19
有没有相同情况的？

做法：求出 $1$ 到每个点的最短路 $f_i$，$n$ 到每个点的最短路 $g_i$。

然后，一个点 $u$ 在最短路上当且仅当存在一条边 $(u,v,c)$，使得 $f_u+c+g_v = f_n$。

一条边 $(u,v)$ 会造成影响，当且仅当以下条件都成立：

• $u,v$ 都在最短路径上。
• 假如只保留最短路径上的边，那么 $v$ 的入度为 $1$。
• $v$ 到达 $n$ 的路径数等于 $1$ 到达 $n$ 的路径数（仅统计最短路径）

对拍了上千组没问题，有没有大佬来救我啊。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=1e6+5;
int n,m;
struct EDGE{
    int to,nxt;
    int id;
    ll col;
};
struct G{
    EDGE edge[maxn*2];
    int cnt;
    int head[maxn];
    void add(int u,int to,int id,ll w){
        edge[++cnt].to=to;
        edge[cnt].col=w;
        edge[cnt].id=id;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
}g1,g2;
ll dis[maxn];
bool vis[maxn];
ll fdis[maxn];
bool ok[maxn];
ll ways_to_n[maxn];
bool ans[maxn];
int ind[maxn];
const ll mod=10000000000000453;
void solve(int id_of_test){
	read(n);
    read(m);
    FOR(i,1,m){
        int a,b;
        ll c;
        read(a);
        read(b);
        read(c);
        g1.add(a,b,i,c);
        g1.add(b,a,i,c);
    }
    {// dijkstra
        priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
        FOR(i,1,n)dis[i]=1e18;
        dis[1]=0;
        q.push(mkpr(0,1));
        while(!q.empty()){
            int u=q.top().se;
            q.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(int i=g1.head[u];i;i=g1.edge[i].nxt){
                int to=g1.edge[i].to;
                if(dis[to]>dis[u]+g1.edge[i].col){
                    dis[to]=dis[u]+g1.edge[i].col;
                    q.push(mkpr(dis[to],to));
                }
            }
        }
    }   
    {// f-dijkstra
        memset(vis,0,sizeof vis);
        priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
        FOR(i,1,n)fdis[i]=1e18;
        q.push(mkpr(0,n));
        fdis[n]=0;
        ways_to_n[n]=1;
        while(!q.empty()){
            int u=q.top().se;
            q.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(int i=g1.head[u];i;i=g1.edge[i].nxt){
                int to=g1.edge[i].to;
                if(fdis[to]>fdis[u]+g1.edge[i].col){
                    fdis[to]=fdis[u]+g1.edge[i].col;
                    ways_to_n[to]=ways_to_n[u];
                    q.push(mkpr(fdis[to],to));
                }else if(fdis[to]==fdis[u]+g1.edge[i].col){
                    ways_to_n[to]+=ways_to_n[u];
                }
                ways_to_n[to]%=mod;
            }
        }
    }   
    FOR(i,1,n){
     //   printf("dis[%d] = %lld\n",i,dis[i]);
    //    printf("fdis[%d] = %lld\n",i,fdis[i]);
     //   printf("ways[%d] = %lld\n",i,ways_to_n[i]);
    }
    {
        ok[n]=1;
        FOR(u,1,n){
    //        printf("u = %d dis %lld fdis %lld\n",u,dis[u],fdis[u]);
           for(int i=g1.head[u];i;i=g1.edge[i].nxt){
                int to=g1.edge[i].to;
                if(dis[u]+g1.edge[i].col+fdis[g1.edge[i].to]==dis[n]){
                    ok[u]=ok[to]=1;
              //      printf("ok u\n",u);
                }
            }
        }
        FOR(u,1,n){
            if(!ok[u])ways_to_n[u]=0;
            for(int i=g1.head[u];i;i=g1.edge[i].nxt){
                int to=g1.edge[i].to;
                if(ok[u]&&ok[to]&&(dis[u]+g1.edge[i].col+fdis[g1.edge[i].to]==dis[n])){
                    g2.add(u,to,g1.edge[i].id,g1.edge[i].col);
                    ind[g1.edge[i].to]++;
                }
            }
        }
    }
    {
        FOR(u,1,n){
            for(int i=g2.head[u];i;i=g2.edge[i].nxt){
                int to=g2.edge[i].to;
              //  printf("%d -> %d\n",u,g2.edge[i].to);
                if(ind[to]==1){
                    if(ways_to_n[to]==ways_to_n[1]){
                        ans[g2.edge[i].id]=1;
                    }
                }
            }
        }
    }
    FOR(i,1,m){
        puts(ans[i]?"Yes":"No");
    }
}
signed main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}