【模板】负环
注意记录入队并判断的过程写在第二个if后稳健，为了防止重边！

#include <bits/stdc++.h>
using namespace std;
const int MAX=2005;
struct node {
	int y,v;
	node (int yy,int vv) {
		y=yy;
		v=vv;
	}
};
vector<node> g[MAX];
bool vis[MAX];
int dis[MAX];
int cnt[MAX];
int n,e;

bool spfa(int s) {
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int f=q.front();
		q.pop();
		vis[f]=false;
		for (int i=0;i<g[f].size();i++) {
			int ny=g[f][i].y;
			int nv=g[f][i].v;
			if (dis[f]+nv<dis[ny]) {
				dis[ny]=dis[f]+nv;
				if (!vis[ny]) {
					if (++cnt[ny]>=n) 
						return false;
					vis[ny]=true;
					q.push(ny);
				}
			}
		}
	}
	return true;
}

int main() {
	int t;
	cin>>t;
	while (t--) {
		memset(dis,0X3F,sizeof(dis));
		memset(vis,0,sizeof(vis));
		memset(cnt,0,sizeof(cnt));
		for (int i=0;i<MAX;i++) g[i].clear();
		cin>>n>>e;
		for (int i=1;i<=e;i++) {
			int x,y,v;
			cin>>x>>y>>v;
			g[x].push_back(node(y,v));
			if (v>=0)
				g[y].push_back(node(x,v));
		}
		puts(spfa(1)?"NO":"YES");
	}
	return 0;
}