单测试点有多组测试数据,注意fill手动清空
const int inf=0x3f3f3f3f;
const int N=2010,M=6010;
int n,m;
int e[M],ne[M],w[M],h[N],idx;
int d[N],cnt[N],vis[N];
void add(int a,int b,int c){
e[idx]=b;w[idx]=c;
ne[idx]=h[a];h[a]=idx++;
}
bool spfa(){ //判负环,存在返回true
fill(d,d+n+1,inf);
fill(vis,vis+n+1,0);
fill(cnt,cnt+n+1,0);
queue<int>q;
q.push(1); vis[1]=1; d[1]=0;
while(q.size()){
int u=q.front();q.pop();vis[u]=0;
for(int i=h[u];i!=-1;i=ne[i]){
int v=e[i];
if(d[v]>d[u]+w[i]){
d[v]=d[u]+w[i];
cnt[v]=cnt[u]+1;
if(cnt[v]>=n)return 1;//判边数
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
return 0;
}
int main(){
int T; scanf("%d",&T);
while(T--){
idx=0;
scanf("%d%d",&n,&m);
fill(h,h+n+1,-1);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
if(w>=0)add(v,u,w);;
}
puts(spfa()?"YES":"NO");
}
return 0;
}