【题目描述】

你的城市正在举办一场密室逃脱挑战赛，你作为参赛选手被关在一个大型数字迷宫里：

迷宫里有 $N$ 个密室，每个密室门上印着一个随机数字 $x_i$, 迷宫设计师提前在 $M$ 条连接密室的通道入口处刻下了数字规则：

• 每条通道直接连接两个不同的密室 $u$ 和 $v$ , 通道处有一个整数值 $w$
• 无论从 $u$ 走到 $v$ 还是从 $v$ 走到 $u$, 数字差必须与通道上的 $w$ 保持一致, 即 $x_v=x_u+w,x_u=x_v-w$

裁判已经保证这个迷宫绝对存在至少一种合法的数字填写方案，你只需要输出任意一种完全符合所有通道规则的数字序列，就能解锁全部密室通关。

【输入格式】

第一行输入两个正整数 $N, M$, 分别代表密室总数量、通道总数量

接下来 $M$ 行，每行三个整数 $u,v,w$, 表示密室 $u$ 与 密室 $v$ 之间存在通道, 且通道的整数值为 $w$

【输出格式】

输出一行 $N$ 个整数 $x_1,x_2,...,x_n$，依次代表 $1,2,\dots,N$ 号密室门上的数字, 用空格隔开$(-10^{18}\le x_i\le 10^{18})$。

若有多组合法的答案,输出任意一组答案即可。

【样例 1】

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

3 5 2

【样例 1 解释】

$1\sim 3$ 号密室们的数值满足 $x_2-x_1=2$、$x_2-x_3=3$、$x_3-x_1=-1$，完全符合所有边的约束，是一个合法解。

【样例 2】

4 2
2 1 5
3 4 -3

5 0 6 3

【样例 3】

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

200401298 182231955 -106709603 69445364 278499365

【数据规模与约定】

对于全部的测试点，保证：

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le \min\left(2 \times 10^5, \frac{N(N-1)}{2}\right)$
• $1 \le u,v \le N$，且 $u \neq v$
• 保证没有重复通道且 $|w| \le 10^9$
• 题目保证输入一定存在至少一个合法解。