https://www.luogu.com.cn/problem/P3385

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
const long long INF=2147483647;
int vis[maxn];
int cnt[maxn];
int dis[maxn];
int n,m,s;
struct node{
    int s1;
    int side;
};
vector<node>mp[maxn];
int Spfa(int s){
    queue<int>v;   
    vis[s]=1;
    v.push(s);
    dis[s]=0;
    while(!v.empty()){
        int q=v.front();
        v.pop();

        vis[q]=1;
        for (int i=0;i<mp[q].size();i++){
            if (dis[mp[q][i].s1]>dis[q]+mp[q][i].side){
                vis[mp[q][i].s1]=0;
                cnt[mp[q][i].s1]++;
                if(cnt[mp[q][i].s1]>=n) return 1;
                dis[mp[q][i].s1] = dis[q] + mp[q][i].side;
                if(vis[mp[q][i].s1]) continue;
                v.push(mp[q][i].s1);      
            }

        }
    }
    return 0;
}
int main()
{
    int x,y,r,t;
    cin>>t;
    while(t--){
        for (int i = 1; i <= n; i++) {
            dis[i]=INF;
            vis[i]=0;
        }
        memset(cnt,0,sizeof(cnt));
        memset(mp,0,sizeof(mp));
        cin>>n>>m;
        while(m--){
            node h;
            cin>>x>>y>>r;
            if(r>=0){
                h.s1=y;
                h.side=r;
                mp[x].push_back(h);
                h.s1=x;
                h.side=r;
                mp[y].push_back(h);
            }
            else{
                h.s1=y;
                h.side=r;
                mp[x].push_back(h);
            }

        }
        if(Spfa(1)) cout<<"YES\n";
        else cout<<"NO\n";
    }
}