CF1387A.Graph

You are given an undirected graph where each edge has one of two colors: black or red.

Your task is to assign a real number to each node so that:

• for each black edge the sum of values at its endpoints is $1$;
• for each red edge the sum of values at its endpoints is $2$;
• the sum of the absolute values of all assigned numbers is the smallest possible.

Otherwise, if it is not possible, report that there is no feasible assignment of the numbers.

给你一个无向图，其中每条边具有两种颜色之一：黑色或红色。

你的任务是为每个节点分配一个实数，使得：

• 对于每条黑边，其两个端点处的数值之和为 $1$；
• 对于每条红边，其两个端点处的数值之和为 $2$；
• 所有分配数值的绝对值之和尽可能小。

否则，若不存在满足条件的赋值方案，则报告不存在可行的数值分配。

The first line contains two integers $N$ ($1 \leq N \leq 100\,000$) and $M$ ($0 \leq M \leq 200\,000$): the number of nodes and the number of edges, respectively. The nodes are numbered by consecutive integers: $1, 2, \ldots, N$.

The next $M$ lines describe the edges. Each line contains three integers $a$, $b$ and $c$ denoting that there is an edge between nodes $a$ and $b$ ($1 \leq a, b \leq N$) with color $c$ ($1$ denotes black, $2$ denotes red).

第一行包含两个整数 $N$（$1 \leq N \leq 100\,000$）和 $M$（$0 \leq M \leq 200\,000$）：分别为节点数和边数。节点编号为连续整数：$1, 2, \ldots, N$。

接下来的 $M$ 行描述各条边。每行包含三个整数 $a$、$b$ 和 $c$，表示节点 $a$ 与节点 $b$（$1 \leq a, b \leq N$）之间存在一条颜色为 $c$ 的边（$1$ 表示黑色，$2$ 表示红色）。

If there is a solution, the first line should contain the word "YES" and the second line should contain $N$ space-separated numbers. For each $i$ ($1 \le i \le N$), the $i$-th number should be the number assigned to the node $i$.

Output should be such that:

• the sum of the numbers at the endpoints of each edge differs from the precise value by less than $10^{-6}$;
• the sum of the absolute values of all assigned numbers differs from the smallest possible by less than $10^{-6}$.

If there are several valid solutions, output any of them.

If there is no solution, the only line should contain the word "NO".

如果存在解，则第一行应包含单词“YES”，第二行应包含 $N$ 个用空格分隔的数字。对于每个 $i$（$1 \le i \le N$），第 $i$ 个数字应为分配给节点 $i$ 的数值。

输出需满足以下条件：

• 每条边两个端点处数值之和与精确值的差的绝对值小于 $10^{-6}$；
• 所有分配数值的绝对值之和与可能的最小值的差的绝对值小于 $10^{-6}$。

若存在多个合法解，输出任意一个即可。

若无解，则仅输出一行单词“NO”。

Note that in the second example the solution is not unique.

注意，在第二个例子中，解不是唯一的。