rt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1<<30
const int N = 1e5 + 10;
int d[N],vis[N],inqueue[N];
int n, m, s, u, v, w,T;
struct node {
	int to, v;
};
vector<node> e[N];
queue<int> q;
bool SPFA(int s, int total) {
	memset(inqueue, 0, sizeof(inqueue)); memset(vis, 0, sizeof(vis));
	while (!q.empty())q.pop();
	for (int i = 1; i <= n; i++)d[i] = INF;
	d[s] = 0; vis[s] = 1, inqueue[s]++; q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop(); vis[u] = 0;
		for (int i = 0, sz = e[u].size(); i < sz; i++) {
			if (d[e[u][i].to] > d[u] + e[u][i].v) {
				d[e[u][i].to] = d[u] + e[u][i].v;
				if (!vis[e[u][i].to]) {
					vis[e[u][i].to] = 1;
					inqueue[e[u][i].to]++;
					q.push(e[u][i].to);
					if (inqueue[e[u][i].to] > total) {
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main() {
	//freopen("C:\\Users\\Administrator\\Downloads\\P3385_1.in", "r", stdin);
	cin >> T;
	while (T--) {
		e->clear();
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%d", &u, &v, &w);
			e[u].push_back({ v,w });
			if (w >= 0) {
				e[v].push_back({ u,w });
			}
		}
		if (SPFA(1,n)) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
}

只有36分