WA on #12 spfa求教 玄关

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int t,n,m,u,v,ww;
int w[N],dist[N],cnt[N];
bool in[N];
struct edge{
	int to,w;
//	edge(int t,int ww){
//		to=t;
//		w=ww;
//	}
};
vector<edge> g[N];

bool spfa(){
	memset(dist,0,sizeof(dist));
	memset(cnt,0,sizeof(cnt));
	memset(in,0,sizeof(in));
	queue<int> q;
    for(int i=1;i<=n;i++){
    	q.push(i);
    	in[i]=1;
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		in[u]=0;
		for(auto ne:g[u]){
			int v=ne.to;
			int w=ne.w;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>(n-1)) return true;
				if(!in[v]){
					q.push(v);
					in[v]=1;
				}
			}
		}
	}
	return false;

}
int main(){
	int w;
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			g[i].clear();
		}
		for(int i=1;i<=m;i++){
			cin>>u>>v>>w;
			if(w>=0) g[v].push_back(edge{u,w});
			g[u].push_back(edge{v,w});
		}
		if(spfa()){
			cout<<"YES"<<'\n';
		} 
		else cout<<"NO"<<'\n';
	}
	return 0;
}