WA on #1#2#9

#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> > g[100001];
int vis[100001], dis[100001], cnt[100001];
const int inf = 0x3f3f3f3f;
bool spfa(int n) {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
	}
	dis[1] = 0;
	vis[1] = 1;
	q.push(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (auto t : g[u]) {
			int v = t.first, w = t.second;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!vis[v]) {
					q.push(v);
					vis[v] = 1;
					cnt[v]++;
					if (cnt[v] > n) return 1;
				}
			}
		}
		vis[u] = 0;
	}
	return 0;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
		    g[i].clear(); 
		    vis[i] = 0;   
		    cnt[i] = 0;   
		}
		for (int i = 1; i <= m; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			if (w > 0) { g[u].push_back({v, w}); g[v].push_back({u, w}); }
			else { g[u].push_back({v, w}); }
		}
		if (spfa(n)) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}