解题思路

把每条约束

看成点 $i,j$ 之间的一条差分关系。

如果我们设某个连通块内任选一个点的值为基准，那么这个连通块中所有点的值都会被唯一确定到“相对值”。这类问题本质上就是：

题目内容

在幻光实验室中，Alice 需要构造一个长度为 $n$ 的正整数数组 $a$，其中每个元素 $a_i > 0$。但她手中有 $m$ 条魔法约束，每条约束给出三元组 $(i,j,k)$，要求 $a_i - a_j = k$。 请你判断是否存在满足所有约束且 $1 \le a_i \le 10^{18}$ 的数组 $a$。若存在则输出任意一个符合条件的数组；否则输出 -1。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 \le T \le 10^5)$ 代表测试组数，每组测试数据描述如下：

第一行输入两个整数 $n,m(1 \le n,m \le 2 \times 10^5)$；

接下来 $m$ 行，每行输入三个整数 $i,j,k$ ($1 \le i,j \le n$，$-10^6 \le k \le 10^6$)

保证所有测试中 $n$ 的总和不超过 $5 \times 10^5$。$m$ 的总和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行： 若存在满足所有约束且 $1 \le a_i \le 10^{18}$ 的数组$a$，则输出 $n$ 个正整数 $a_1,a_2,\dots,a_n$；否则输出 -1。

样例1

输入

2
3 2
1 2 1
2 3 1
2 2
1 2 100
2 1 1

输出

3 2 1
-1