code
#include <cstdio>
#include <cctype>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 2e3 + 10, M = 6e3 + 10;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N], cnt[N], hh, tt;
bitset<N> st;
inline void add(register int a, register int b, register int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
inline void init()
{
hh = 0, tt = 1, idx = 0;
memset(h, -1, sizeof h);
memset(cnt, 0, sizeof cnt);
memset(dist, 0, sizeof dist);
st.reset();
}
inline int spfa()
{
for (register int i = 1; i <= n; i ++ )
{
q[tt ++ ] = i;
if (tt == N)
tt = 0;
st[i] = 1;
}
while (hh != tt)
{
register int u = q[hh ++ ];
if (hh == N)
hh = 0;
st[u] = 0;
for (register int i = h[u]; ~i; i = ne[i])
{
register int j = e[i];
if (dist[j] > dist[u] + w[i])
{
dist[j] = dist[u] + w[i];
cnt[j] = cnt[u] + 1;
if (cnt[j] >= n)
return 1;
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N)
tt = 0;
st[j] = 1;
}
}
}
}
return 0;
}
template<typename T> inline void read(register T &qwq)
{
register T x = 0, f = 1;
register char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
qwq = x * f;
return;
}
int main()
{
register int T;
read(T);
while (T -- )
{
init();
read(n), read(m);
for (register int i = 1, a, b, c; i <= m; i ++ )
{
read(a), read(b), read(c);
if (c < 0)
add(a, b, c);
else add(a, b, c), add(b, a, c);
}
if (spfa())
puts("YES");
else puts("NO");
}
return 0;
}