题目描述

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

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

输入格式

本题单个测试点包含多组测试数据。

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

第一行有两个整数 $n$ 和 $m$，分别表示图的顶点数和下面将给出的边信息条数。

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

• 若 $w \geq 0$，则表示同时存在一条从 $u$ 到 $v$、权值为 $w$ 的边，以及一条从 $v$ 到 $u$、权值为 $w$ 的边。
• 若 $w \lt 0$，则仅表示存在一条从 $u$ 到 $v$、权值为 $w$ 的边。

输出格式

对于每组测试数据，输出一行。若所求负权环存在则输出 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 \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$ 表示边信息的条数，不一定是图的实际边数（当 $w \geq 0$ 时一条信息对应两条边）。