P6696 [BalticOI 2020] 图 (Day2)

你有一个无向图，每条边都有一种颜色：红或者黑。 你要做的就是为每个节点配一个实数点权，使得： - 对于每条黑色边，两个端点的点权之和为 $1$ - 对于每条红色边，两个端点的点权之和为 $2$ - 所有点权的绝对值之和是最小的 求一种点权的分配方案。

第一行两个整数 $N,M$ 代表点数和边数。 所有点的编号为 $1$ 到 $N$。 接下来 $M$ 行每行三个整数 $a,b,c$ 描述一条边端点为 $a$ 和 $b$，如果 $c$ 是 $1$ 那么这条边是黑色边，如果 $c$ 是 $2$ 那么这条边是红色边。

如果有解，首先第一行输出 `YES`，然后第二行 $N$ 个整数代表可能的一组点权。 多组解输出任意一组即可。 如果无解，一行一个字符串 `NO`。

#### 评测方式 您的输出被评判为正确，当且仅当： - 每条边所连两点的点权和与该边要求的点权间的误差不超过 $10^{-6}$。 - 所有点权的绝对值之和与标准答案误差不超过 $10^{-6}$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$N \le 5$，$M \le 14$。 - Subtask 2（12 pts）：$N \le 100$。 - Subtask 3（17 pts）：$N \le 1000$。 - Subtask 4（24 pts）：$N \le 10^4$。 - Subtask 5（42 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le M \le 2 \times 10^5$。 **本题使用 Special Judge。**