80分求助WA#1#9

using namespace std;
#include<bits/stdc++.h>
#define ll long long
const ll N=2e3+10;
const ll M=3e3+33;
ll cntt=0;ll head[N];
ll vis[N];ll n,m;ll t;
ll cnt[N];
ll dis[N];
ll flag=0;
queue<ll> q;
struct edge{
	ll to,nxt,w;
}ed[M<<2];
void clearr(){
	cntt=0;
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	memset(head,0,sizeof(head));
	memset(dis,0x7f,sizeof(dis));
	while (!q.empty()) q.pop();
	flag=0;
}
void add_t(ll u,ll v,ll w){
	ed[++cntt].to=v;
	ed[cntt].nxt=head[u];
	ed[cntt].w=w;
	head[u]=cntt;
}

int main(){
//	freopen("P3385_1.in","r",stdin);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>t;
	for(int d=1;d<=t;d++){
		clearr();
		cin>>n>>m;
		for(int j=1;j<=m;j++){
			ll u,v,w;
			cin>>u>>v>>w;
			add_t(u,v,w);
			if(w>=0){
				add_t(v,u,w);
			}
		}
		dis[1]=0;
		vis[1]=1;
		q.push(1);
		while(!q.empty()){
			ll u=q.front();
			q.pop();vis[u]=0;
			if(cnt[u]==n-1){
				flag=1;break;
			}
			cnt[u]++;
			for(int i=head[u];i;i=ed[i].nxt){
				ll v=ed[i].to;ll ww=ed[i].w;
				if(vis[v])continue;
				if(dis[v]>dis[u]+ww){
					dis[v]=dis[u]+ww;
					if(!vis[v])vis[v]=1,q.push(v);
				}
			}
		}
		if(flag==1){
			cout<<"YES\n";
		}else{
			cout<<"NO\n";
		}
	}
	return 0;
}

1
9 16
1 2 -4
1 4 0
1 7 -4
1 4 9
2 3 -2
2 8 -3
2 5 11
2 5 4
2 7 6
3 5 -3
3 7 11
4 8 1
5 6 -2
5 6 8
6 9 -4
7 9 0