CF1850H.The Third Letter

In order to win his toughest battle, Mircea came up with a great strategy for his army. He has $n$ soldiers and decided to arrange them in a certain way in camps. Each soldier has to belong to exactly one camp, and there is one camp at each integer point on the $x$-axis (at points $\cdots, -2, -1, 0, 1, 2, \cdots$).

The strategy consists of $m$ conditions. Condition $i$ tells that soldier $a_i$ should belong to a camp that is situated $d_i$ meters in front of the camp that person $b_i$ belongs to. (If $d_i \lt 0$, then $a_i$'s camp should be $-d_i$ meters behind $b_i$'s camp.)

Now, Mircea wonders if there exists a partition of soldiers that respects the condition and he asks for your help! Answer "YES" if there is a partition of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.

Note that two different soldiers may be placed in the same camp.

为了赢得最艰难的一场战役，米尔恰为他的军队制定了一项精妙的战略。他有 $n$ 名士兵，并决定以某种方式将他们安排在营地中。每名士兵必须且只能属于一个营地，而 $x$ 轴上的每个整数点（即点 $\cdots, -2, -1, 0, 1, 2, \cdots$）都设有一个营地。

该战略包含 $m$ 条约束条件。第 $i$ 条约束条件指出：士兵 $a_i$ 所属的营地必须位于士兵 $b_i$ 所属营地前方 $d_i$ 米处。（若 $d_i < 0$，则表示 $a_i$ 所属营地应在 $b_i$ 所属营地后方 $-d_i$ 米处。）

现在，米尔恰想知道是否存在一种士兵分组方案，使其满足全部约束条件，并请求你的帮助！若存在一种将 $n$ 名士兵划分到营地的方案，使得全部 $m$ 条约束均被满足，则输出 "YES"；否则输出 "NO"。

注意：两名不同的士兵可以被安排在同一个营地。

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains two positive integers $n$ and $m$ ($2 \leq n \leq 2 \cdot 10^5$; $1 \leq m \leq n$) — the number of soldiers, and the number of conditions respectively.

Then $m$ lines follow, each of them containing $3$ integers: $a_i$, $b_i$, $d_i$ ($a_i \neq b_i$; $1 \leq a_i, b_i \leq n$; $-10^9 \leq d_i \leq 10^9$) — denoting the conditions explained in the statement. Note that if $d_i$ is positive, $a_i$ should be $d_i$ meters in front of $b_i$ and if it is negative, $a_i$ should be $-d_i$ meters behind $b_i$.

Note that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$；$1 \leq m \leq n$），分别表示士兵的数量和条件的数量。

接下来是 $m$ 行，每行包含 $3$ 个整数：$a_i$、$b_i$、$d_i$（$a_i \neq b_i$；$1 \leq a_i, b_i \leq n$；$-10^9 \leq d_i \leq 10^9$），表示题目陈述中所述的条件。注意：若 $d_i$ 为正，则 $a_i$ 应位于 $b_i$ 前方 $d_i$ 米处；若 $d_i$ 为负，则 $a_i$ 应位于 $b_i$ 后方 $-d_i$ 米处。

注意：所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output "YES" if there is an arrangement of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.

对于每个测试用例，如果存在一种 $n$ 名士兵的排列方式满足全部 $m$ 个条件，则输出 “YES”，否则输出 “NO”。

For the first test case, we can partition the soldiers into camps in the following way: soldier:

• Soldier $1$ in the camp with the coordinate $x = 3$.
• Soldier $2$ in the camp with the coordinate $x = 5$.
• Soldier $3$ in the camp with the coordinate $x = 9$.
• Soldier $4$ in the camp with the coordinate $x = 11$.

For the second test case, there is no partition that can satisfy all the constraints at the same time.

For the third test case, there is no partition that satisfies all the constraints since we get contradictory information about the same pair.

For the fourth test case, in order to satisfy the only condition, a possible partition is:

• Soldier $1$ in the camp with the coordinate $x = 10$.
• Soldier $2$ in the camp with the coordinate $x = 13$.
• Soldier $3$ in the camp with the coordinate $x = -2023$.
• Soldier $4$ in the camp with the coordinate $x = -2023$.

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

• 士兵 $1$ 分配到坐标为 $x = 3$ 的营地；
• 士兵 $2$ 分配到坐标为 $x = 5$ 的营地；
• 士兵 $3$ 分配到坐标为 $x = 9$ 的营地；
• 士兵 $4$ 分配到坐标为 $x = 11$ 的营地。

对于第二个测试用例，不存在一种分配方案能同时满足所有约束条件。

对于第三个测试用例，不存在满足所有约束条件的分配方案，因为我们关于同一对士兵得到了相互矛盾的信息。

对于第四个测试用例，为满足唯一约束条件，一种可行的分配方案是：

• 士兵 $1$ 分配到坐标为 $x = 10$ 的营地；
• 士兵 $2$ 分配到坐标为 $x = 13$ 的营地；
• 士兵 $3$ 分配到坐标为 $x = -2023$ 的营地；
• 士兵 $4$ 分配到坐标为 $x = -2023$ 的营地。