题目描述

为了赢得他最艰难的战斗，光头强为他的军队制定了一个出色的战略。他有 $n$ 名士兵，并决定以一定的方式将它们安排在营地中。每名士兵必须属于一个特定的营地，并且在 $x$ 轴上的每个整数点（在点⋯，-2，-1，0，1，2，⋯）上都有一个营地。

这个战略包括 $m$ 个条件。第 $i$ 个条件告诉我们，士兵 $a_i$ 应该属于距离士兵 $b_i$ 所在的营地左边 $d_i$ 米的一个营地。（如果 $d_i<0$，则 $a_i$ 的营地应该在 $b_i$ 的营地右边 $-d_i$ 米处。）

现在，光头强想知道是否存在一种士兵的划分，使得所有 $m$ 个条件都得到满足，他请求你的帮助！如果存在满足所有 $m$ 个条件的 $n$ 名士兵的划分，请回答YES，否则回答 NO。

请注意，两个不同的士兵可能被放置在同一个营地。

输入格式

第一行包含一个整数 $t(1≤t≤100)$ ——测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $m(2≤n≤2×10^5；1≤m≤n)$ ——士兵的数量和条件的数量。

然后是 $m$ 行，每行包含 $3$ 个整数：$a_i$、$b_i$、$d_i(a_i≠b_i；1≤a_i,b_i≤n；-10^9≤d_i≤10^9)$ ——表示说明中的条件。请注意，如果 $d_i$ 为正，$a_i$ 应该在 $b_i$ 左边 $d_i$ 米，如果为负，则 $a_i$ 应该在 $b_i$ 的右边 $-d_i$ 米处。

请注意，所有测试用例中 $n$ 的总和不超过 $2×10^5$。

输出格式

对于每个测试用例，如果存在一个满足所有 $m$ 个条件的 $n$ 名士兵的安排，请输出 YES，否则输出 NO。

测试样例

4
5 3
1 2 2
2 3 4
4 2 -6
6 5
1 2 2
2 3 4
4 2 -6
5 4 4
3 5 100
2 2
1 2 5
1 2 4
4 1
1 2 3

YES
NO
NO
YES

样例说明

对于第一个测试用例，我们可以按照以下方式将士兵划分到营地中：士兵：

• 士兵1 在坐标 $x=3$ 的营地中。
• 士兵2 在坐标 $x=5$ 的营地中。
• 士兵3 在坐标 $x=9$ 的营地中。
• 士兵4 在坐标 $x=11$ 的营地中。

对于第二个测试用例，没有一种划分方式可以同时满足所有的约束条件。

对于第三个测试用例，由于我们得到了关于同一对士兵的矛盾信息，因此不存在满足所有条件的划分方式。

对于第四个测试用例，为了满足唯一的条件，一种可能的划分方式是：

• 士兵1 在坐标 $x=10$ 的营地中。
• 士兵2 在坐标 $x=13$ 的营地中。
• 士兵3 在坐标 $x=-2023$ 的营地中。
• 士兵4 在坐标 $x=-2023$ 的营地中。