#include<iostream>
#include<queue>
#include<cstring>
#include<fstream>
using namespace std;
ifstream ifs("data.in");
const int M = 3003, N = 2003;
int to[M << 1], edge[M << 1], nxt[M << 1], head[N], tot;
int cnt[N], dis[N];
bool v[N];
int n, m;
void init()
{
	memset(to, 0, sizeof(to)),
		memset(edge, 0, sizeof(edge)),
		memset(nxt, 0, sizeof(nxt)),
		memset(head, 0, sizeof(head)),
		memset(cnt, 0, sizeof(cnt)),
		memset(dis, 0x3f, sizeof(dis));
	memset(v, 0, sizeof(v));
	tot = 0;
}
void add(int f, int t, int v)
{
	to[++tot] = t, edge[tot] = v, nxt[tot] = head[f], head[f] = tot;
}
bool spfa()
{
	queue<int>q;
	q.push(1), dis[1] = 0, v[1] = 1;
	while (!q.empty())
	{
		int p = q.front();
		q.pop(), v[p] = 0;
		if (cnt[p] >= n)
		{
			cout << "YES\n";
			return 1;
		}
		for (int i = head[p]; i; i = nxt[i])
		{
			if (dis[to[i]] > dis[p] + edge[i])
			{
				dis[to[i]] = dis[p] + edge[i];
				cnt[to[i]] = cnt[p] + 1;
				if (!v[to[i]])
				{
					q.push(to[i]), v[to[i]] = 1;
				}
			}
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	ifs >> t;
	while (t--)
	{
		ifs >> n >> m;
		for (int i = 0, a, b, c; i < m; i++)
		{
			ifs >> a >> b >> c;
			if (c >= 0)
				add(a, b, c), add(b, a, c);
			else
				add(a, b, c);
		}
		if (!spfa())
			cout << "NO\n";
		init();
	}
	return 0;
}

第一篇题解里的两个hack数据可以过