解题思路
把每条约束
ai−aj=k
看成点 i,j 之间的一条差分关系。
如果我们设某个连通块内任选一个点的值为基准，那么这个连通块中所有点的值都会被唯一确定到“相对值”。这类问题本质上就是：
P4710.第2题-约束差值数组
题目内容
在幻光实验室中，Alice 需要构造一个长度为 n 的正整数数组 a，其中每个元素 ai>0。但她手中有 m 条魔法约束，每条约束给出三元组 (i,j,k)，要求 ai−aj=k。 请你判断是否存在满足所有约束且 1≤ai≤1018 的数组 a。若存在则输出任意一个符合条件的数组；否则输出 -1。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤105) 代表测试组数，每组测试数据描述如下：
第一行输入两个整数 n,m(1≤n,m≤2×105)；
接下来 m 行，每行输入三个整数 i,j,k (1≤i,j≤n，−106≤k≤106)
保证所有测试中 n 的总和不超过 5×105。m 的总和不超过 5×105。
输出描述
对于每组测试数据，输出一行：
若存在满足所有约束且 1≤ai≤1018 的数组a，则输出 n 个正整数 a1,a2,…,an；否则输出 -1。
样例1
输入
2
3 2
1 2 1
2 3 1
2 2
1 2 100
2 1 1
输出
3 2 1
-1
