题目内容

在一个精密实验室中，有 $n$ 台仪器需要校准。 已知这些仪器之间存在 $m$ 组确定的读数偏差关系，每组关系表示为： 仪器 $i$ 的读数比仪器 $j$ 的读数恰好高 $k$。

你需要为每一台仪器分配一个正整数的读数 $x_i$，使得所有偏差关系同时成立， 并且每台仪器的读数必须落在 $1$ 到 $10^{18}$ 的范围之内。

请判断是否能够给出这样的读数分配方案。

数据范围与约束

• 仪器台数 $n$ 与偏差关系数 $m$ 均不超过 $2 \times 10^5$。
• 所有测试数据中 $n$ 的总和与 $m$ 的总和均不超过 $5 \times 10^5$。
• 对于每条关系，$i$ 和 $j$ 满足 $1 \le i, j \le n$，$k$ 的绝对值不超过 $10^6$。
• 每个读数必须为正整数且不超过 $10^{18}$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。 接下来依次描述每组数据，格式如下： 第一行包含两个整数 $n$ 和 $m$，分别表示仪器台数和偏差关系条数。 接下来 $m$ 行，每行包含三个整数 $i$、$j$ 和 $k$，表示仪器 $i$ 的读数应比仪器 $j$ 的读数高 $k$。 保证 $1 \le i, j \le n$，$|k| \le 10^6$。

输出描述

对于每组测试数据，输出一行： 如果存在符合要求的读数分配方案，输出 $n$ 个整数 $x_1, x_2, \dots, x_n$，依次表示每台仪器的读数； 如果不存在这样的方案，输出 -1。

样例1

输入

1
3 2
2 1 3
3 2 5

输出

1 4 9

说明

根据关系：仪器 2 比仪器 1 高 3，即 $a_2 = a_1 + 3$；仪器 3 比仪器 2 高 5，即 $a_3 = a_2 + 5 = a_1 + 8$。若取 $a_1 = 1$，则 $a_2 = 4$，$a_3 = 9$，所有读数均在 $[1, 10^{18}]$ 范围内且无矛盾。因此输出 1 4 9。

样例2

输入

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

输出

-1

说明

由 $a_1 - a_2 = 2$ 得 $a_1 = a_2 + 2$；由 $a_2 - a_3 = 3$ 得 $a_2 = a_3 + 3$，代入得 $a_1 = a_3 + 5$。但 $a_3 - a_1 = -4$ 给出 $a_3 = a_1 - 4$，即 $a_1 = a_3 + 4$。这与 $a_1 = a_3 + 5$ 矛盾，因此无法分配，输出 -1。

样例3

输入

1
5 3
1 2 7
3 4 -2
4 5 10

输出

8 1 9 11 1

说明

图中存在两个独立的连通块。 第一个连通块包含仪器 1 和 2，约束 $a_1 - a_2 = 7$。令 $a_2 = 1$，则 $a_1 = 8$。 第二个连通块包含仪器 3、4、5。由 $a_3 - a_4 = -2$ 得 $a_4 = a_3 + 2$；由 $a_4 - a_5 = 10$ 得 $a_5 = a_4 - 10$。若令 $a_5 = 1$，则 $a_4 = 11$，$a_3 = 9$。 所有读数均为正整数且不超过 $10^{18}$，满足全部关系，故输出 8 1 9 11 1。

样例4

输入

1
2 0

输出

1 1

说明

没有任何偏差关系，两台仪器可以独立取最小值 1。该分配满足 $1 \\le a_i \\le 10^{18}$，且无矛盾，因此输出 1 1。