The Third Letter

Description:

Input:

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$$$.

Output:

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.

Sample Input:

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

Sample Output:

YES
NO
NO
YES

Note:

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$$$.