#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2005;

int dis[maxn], cnt[maxn], n;
bool vis[maxn];

struct Edge {
	int v, w;
};

vector <Edge> e[maxn];
queue <int> q;

void add(int u, int v, int w) {
	e[u].push_back((Edge){v, w});
}

void spfa(const int s) {
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	memset(cnt, 0, sizeof(cnt));
	while(q.size()) q.pop();
	dis[s] = 0; vis[s] = 1; //cnt[s] = 1;
	q.push(s);
	while (q.size()) {
		int now = q.front();
		vis[now] = 0; // vis 表示是否在队列里 
		for (int i = 0; i < e[now].size(); i++) {
			int v = e[now][i].v, w = e[now][i].w;
			if (dis[now] + w < dis[v]) {
				dis[v] = dis[now] + w;
				cnt[v] = cnt[now] + 1;
				if (cnt[v] >= n) {
					cout << "YES\n";
					return;
				}
				if (!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
		q.pop();
	}
	cout << "NO\n";
}

signed main() {
	int T, m, u, v, w;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 1; i <= m; i++) {
			cin >> u >> v >> w;
			if (w >= 0) {
				add(u, v, w);
				add(v, u, w);
			} else add(u, v, w);
			
		}
		spfa(1);
	}
}

超的第一篇题解。

或者这个题解长得也差不多： https://www.luogu.com.cn/article/wq5yglhg