80分，求调；WA 4,8

#include<bits/stdc++.h>
using namespace std;

const int MAX=2005;
int T,n,m;

struct Edge{
	int v,w;
};
vector<Edge> e[MAX];

int dis[MAX],cnt[MAX];
bool vis[MAX]; 
queue<int> q;
void SPFA()
{
	memset(vis,false,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	dis[1]=0;
	cnt[1]++;
	q.push(1);
    vis[1]=true;
	while(!q.empty()){
		int k=q.front();
		q.pop();
		vis[k]=false;
		for(int i=0;i<e[k].size();i++){
			int v=e[k][i].v,w=e[k][i].w;
			if(dis[v]>dis[k]+w){
				dis[v]=dis[k]+w;
				if(vis[v]==false){
					q.push(v);
					cnt[v]++;
					vis[v]=true;
					if(cnt[v]>n){
						cout<<"YES"<<"\n";
						return;
					}
				}
			}
		}
	}
	cout<<"NO"<<"\n";
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
        for(int i=1;i<=n;i++) e[i].clear();
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			e[u].push_back({v,w});
            if(w>=0) e[v].push_back({u,w});
		}
		SPFA();
	}
	return 0;
}