409800: GYM103765 E 孤独的小Z

小Z很孤独，他的朋友很少。某天，他做了一个梦，梦到了他有好多朋友，分布在各个城市，他依稀记得梦中各个城市间朋友数量的关系。现在，梦醒了，小Z想要知道这个梦是否有可能是真的。

有n个城市，编号为1 - n，他还依稀记得m条信息，每条信息是下面其中一种：

• 城市a中的朋友数量比城市b中的朋友数量至少多c个。
• 城市a中的朋友数量比城市b中的朋友数量至多多c个。
• 城市a中的朋友数量等于城市b中的朋友数量。

第一行是一个整数T(1 ≤ T ≤ 50)，表示样例的个数。

每个样例第一行有两个整数n, m，表示城市数量和信息数量。

之后m行：

如果该行第一个数字是1，则接下来有三个整数a, b, c，表示城市a中的朋友数量比城市b中的朋友数量至少多c个。

如果该行第一个数字是2，则接下来有三个整数a, b, c，表示城市a中的朋友数量比城市b中的朋友数量至多多c个。

如果该行第一个数字是3，则接下来有三个整数a, b，表示城市a中的朋友数量等于城市b中的朋友数量。

同类型下信息两个城市不会重复同时出现，比如已经出现了有了信息1 2 3 100，不会再出现信息1 2 3 200，但可能出现1 3 2 200。

另外，不会出现重复的信息。

1 ≤ n, m, a, b, c ≤ 1000，a ≠ b

每个样例输出一个整数，如果梦可能为真，则输出小Z最少有多少个朋友。如果梦为假，则输出 - 1。

2
3 3
3 1 2
1 1 3 1
2 2 3 2
2 2
1 1 2 1
1 2 1 1

2
-1