题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的无向简单连通图。图中的顶点编号为 $1$ 到 $N$ 的互不相同的自然数，边的编号为 $1$ 到 $M$ 的互不相同的自然数。

第 $j$ 条边（$1 \leq j \leq M$）连接编号为 $a_j$ 和 $b_j$ 的两个顶点，边的权值为整数 $c_j$。

你需要为每个顶点分配一个整数权值。设第 $i$ 个顶点（$1 \leq i \leq N$）的权值为 $x_i$。

对所有顶点所分配权值的总代价定义为这些权值的绝对值之和，即：

$$|x_1| + |x_2| + \cdots + |x_N| = \sum_{i=1}^{N} |x_i| $$

如果要使图保持平衡，则每一条边连接的两个顶点的权值之和必须等于该边的权值。也就是说，对于所有 $j$（$1 \leq j \leq M$），应满足：

$$x_{a_j} + x_{b_j} = c_j$$

例如，考虑下图中的一个图，它包含 5 个顶点和 4 条边。在图中，圆圈内的数字表示顶点编号，边上的数字表示边的权值。

如果按照下图所示，为各顶点分配权值为 $[2, -7, 3, -5, 0]$，则每一条边连接的两个顶点的权值之和均等于对应边的权值。图中每个圆圈中的数字即为该顶点的权值

该分配方式的总代价为：

$$|2| + |-7| + |3| + |-5| + |0| = 2 + 7 + 3 + 5 + 0 = 17 $$

这是最小可能总代价。

例如，若将各顶点权值设为 $[6, -3, -1, -9, 4]$，尽管此时图仍满足平衡条件，但总代价变为：

$$|6| + |-3| + |-1| + |-9| + |4| = 6 + 3 + 1 + 9 + 4 = 23 $$

这显然不是最优方案。

你的任务是编写一个程序，判断是否存在某种分配方式使图保持平衡，若存在，请输出总代价最小的一种分配方式之一。

输入格式

第一行包含两个整数 $N$ 和 $M$，用一个空格分隔。

接下来 $M$ 行，每行包含三个整数 $a_j$、$b_j$、$c_j$，表示一条边的连接情况和其权值。各整数之间用空格分隔。

输出格式

若存在一种方式为图中每个顶点分配整数权值，使得图保持平衡，则输出：

• 第一行输出 Yes（不区分大小写）
• 第二行输出 $N$ 个整数 $x_1, x_2, \ldots, x_N$，用空格分隔，表示每个顶点的权值。若有多种满足条件的最小总代价方案，可任选其一输出。

若不存在任何一种满足条件的分配方式，则输出：

• 一行输出 No（不区分大小写）

3 3
1 2 5
2 3 4
3 1 3

Yes
2 3 1

5 4
1 3 5
2 3 -4
4 2 -12
5 3 3

Yes
2 -7 3 -5 0

提示

约束条件

• 所有给定数值均为整数。
• $2 \leq N \leq 100\,000$
• $1 \leq M \leq 200\,000$
• 对所有 $j$（$1 \leq j \leq M$），满足：
  • $1 \leq a_j, b_j \leq N$
  • $a_j \ne b_j$（不存在连接同一顶点的边）
  • $-1\,000\,000 \leq c_j \leq 1\,000\,000$
• 对所有 $j < k$（$1 \leq j < k \leq M$），满足 $\{a_j, b_j\} \ne \{a_k, b_k\}$（任意两个顶点对之间至多存在一条边）
• 图是连通的，即任意两个顶点之间都存在路径相连。

子任务

1. （6 分）$N = 3$ 且 $M = 3$，三条边分别连接顶点 1-2、2-3、3-1
2. （10 分）$N \leq 1\,000$ 且 $M = N - 1$，第 $j$ 条边连接顶点 $j$ 和 $j + 1$
3. （11 分）$M = N - 1$ 且第 $j$ 条边连接顶点 $j$ 和 $j + 1$
4. （12 分）$M = N - 1$
5. （13 分）$M = N$ 且每个顶点连接恰好两条不同的边
6. （29 分）$N \leq 1\,000$
7. （19 分）无额外约束条件。