WA on #1 #2

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w[3001][3001],flag,q;
vector<int> vc[3001];
queue<int> qu;
int dis[3001],vis[3001];
void SPFA(){
	while(!qu.empty()){
		int p=qu.front();
		qu.pop();
		for(int i=0;i<vc[p].size();++i){
			int nxt=vc[p][i];
			if(dis[p]+w[p][nxt]<dis[nxt]){
				dis[nxt]=dis[p]+w[p][nxt];
				qu.push(nxt);
				vis[nxt]++;
				if(vis[nxt]>=n){
					flag=1;
					return;
				}
			}
		}
	}
}
void work(){
	cin>>n>>m;
	flag=0;
	while(!qu.empty())qu.pop();
	memset(vis,0,sizeof(vis));
	memset(dis,0x7f,sizeof(dis));
	memset(w,0x7f,sizeof(w));
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		cin>>w[u][v];
		if(w[u][v]>=0){
			vc[v].push_back(u);
			w[v][u]=w[u][v];
		}
		vc[u].push_back(v);
	}
	dis[1]=0;
	qu.push(1);
	vis[1]=1;
	SPFA();
	for(int i=1;i<=n;++i){
		vc[i].clear();
	}
	if(flag){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>q;
	while(q--){
		work();
	}
	return 0;
}