题目描述

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。
负环的定义是：一条边权之和为负数的回路。

输入格式：

第一行一个正整数T表示数据组数；
对于每组数据：
第一行两个正整数N M，表示图有N个顶点，M条边
接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）

输出格式：

共T行。对于每组数据，存在负环则输出一行"YES"，否则输出一行"NO"。

输入样例#1：

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

输出样例#1：

NO
YES

数据范围

对于全部的测试点，保证：

• $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$。

提示

请注意，$m$ 不是图的边数。