题目描述

给定一个有 $n$ 个顶点的有向图。图中可以有重边和自环。请判断从顶点 $1$ 出发是否能够到达某个负环。

负环指沿边的方向绕行一周后回到起点，且所经过的边权之和小于零的回路。

输入格式

一个测试点内包含多组数据。 第一行是整数 $T$，后面依次给出 $T$ 组图。

每组先输入两个整数 $n,m$，即顶点数与接下来描述边的记录数。下面 $m$ 行，每行输入三个整数 $u,v,w$。

• $w\ge0$ 时，加入 $u\to v$ 和 $v\to u$ 两条边，权值都是 $w$。
• $w<0$ 时，仅加入 $u\to v$ 这一条权值为 $w$ 的边。

输出格式

每组输出一行。存在从顶点 $1$ 可达的负环时输出 YES，否则输出 NO。

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

NO
YES

说明/提示

$1\le T\le10$，$1\le n\le2000$，$1\le m\le3000$，$1\le u,v\le n$，$-10^4\le w\le10^4$。

提示

$m$ 统计的是输入记录条数。一条非负权记录会对应两条有向边，因此实际的有向边数可能大于 $m$。