题目描述

给定 $T$ 组测试数据，每组数据包含一个 $n$ 个点、$m$ 条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你判断每组数据对应的图中是否存在负权回路（即总权值为负数的环）。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$，分别表示图的点数和边数。
• 接下来 $m$ 行，每行包含三个整数 $x, y, z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

输出格式

对于每组测试数据，输出一行结果：

• 如果图中存在负权回路，输出 Yes；
• 否则输出 No。

样例 #1

样例输入 1

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

样例输出 1

Yes
No

数据范围

• $1 \le T \le 10$
• $1 \le n \le 2000$
• $1 \le m \le 10000$
• 图中涉及边长绝对值均不超过 $10000$