隐藏权值

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的有向图。第 $j$ 条有向边从顶点 $u_j$ 指向顶点 $v_j$，权值为 $w_j$。

请为每个顶点写一个介于 $-10^{18}$ 和 $10^{18}$（含端点）之间的整数，使得以下条件成立。

设 $x_i$ 为顶点 $i$ 上写的值。对于所有边 $j=1,2,\dots,M$，都有 $x_{v_j} - x_{u_j} = w_j$。

保证对于给定的输入，至少存在一个这样的赋值方案。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$

输出格式

设 $x_i$ 为顶点 $i$ 上写的整数。在一行中按顺序输出 $x_1, x_2, \dots, x_N$，用空格分隔。如果存在多个解，输出其中任意一个即可。

样例

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

3 5 2

令 $x = (3, 5, 2)$，则 $x_2 - x_1 = w_1 = 2$、$x_2 - x_3 = w_2 = 3$、$x_3 - x_1 = w_3 = -1$，满足条件。

例如，$x = (-1, 1, -2)$ 也是一个合法答案。

4 2
2 1 5
3 4 -3

5 0 6 3

例如，$x = (0, -5, 4, 1)$ 和 $x = (5, 0, 4, 1)$ 也都是合法答案。

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\{2 \times 10^5, N(N-1)/2\}$
• $1 \le u_j, v_j \le N$
• $u_j \neq v_j$
• 若 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$ 且 $(u_i, v_i) \neq (v_j, u_j)$
• $|w_j| \le 10^9$
• 输入均为整数
• 保证至少存在一个满足条件的赋值方案

提示

答案不唯一，输出任意合法解即可。