【例题2】负环判断

题目描述

给定一个$n$个点的有向图，请求出图中是否存在从顶点$1$出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

输入的第一行是一个整数$T$，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数$n$和边数$m$。

接下来$m$行，每行三个整数$u$,$v$,$w$。

若$w \geq 0$，则表示存在一条从$u$至$v$边权为$w$的边，还存在一条从$v$至$u$边权为$w$的边。

若$w < 0$，则只表示存在一条从$u$至$v$边权为$w$的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出$YES$，否则输出$N0$。

数据范围与提示

对于$100\%$的数据，满足$1 \leq n \leq 2 \times 10^{3}$，$1 \leq m \leq 3 \times 10^{3}$，$1 \leq u,v \leq n$，$-10^{4} \leq w \leq 10^{4}$，$1 \leq T \leq 10$。

样例

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

N0
YES