P12724 [KOI 2021 Round 2] 图的平衡

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定一个包含 $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`（不区分大小写）

**约束条件** - 所有给定数值均为整数。 - $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 分）无额外约束条件。