题目背景

人面不知何处去, 桃花依旧笑春风.

题目描述

给定一张 $n$ 个结点的无向完全图 $G$, 边 $(i, j)$ 带非负整数权 $v_{i, j}$, 保证 $v_{i, i} = 0$, $v_{i, j} = v_{j, i}$.

同时, 每个结点有一个非负整数变量 $w_i$.

定义对一个点 $i$ 进行一次 收集操作 为, 将 $w_i$ 的值加上 $\sum_j v_{i, j}$, 并将 $w_j$ 的值减去 $v_{i, j}$. 称一次对点 $i$ 的收集操作 合法, 当且仅当操作前 $w_j \ge v_{i, j}$.

在图 $G$ 上称一组点权 收集-free, 当且仅当以这组点权为初始状态, 存在一种方式, 能够进行 无限次 合法的收集操作.

你有 两种 任务. 第一种, 构造 一组点权 $w'_i$, 使得 $w'_i$ 收集-free, 且 最小化 $\sum_i w'_i$; 第二种, 给定一组点权 $w'_i$, 你需要 判断 $w'_i$ 是否 收集-free.

输入格式

第一行一个正整数 $o$, 表示你的任务类型.

第二行一个正整数 $n$ 和一个非负整数 $m$, 表示 $G$ 的结点数和边权非 0 的边数.

接下来的 $m$ 行, 每行 3 个正整数 $i$, $j$, $v$, 表示在 $i$ 和 $j$ 间的边边权为 $v$.

若 $o=2$, 接下来有一行 $n$ 个非负整数 $w'_i$, 代表你需要判断是否 收集-free 的一组点权.

输出格式

若 $o=1$, 输出一行 $n$ 个非负整数 $w'_i$, 代表你构造的点权. 你应当保证 $0 \le w'_i \le 10^{18}$.

若 $o=2$, 输出一行 YES 或 NO, 代表 $w'_i$ 是否 收集-free.

样例

样例输入 1

1
5 6
1 2 1
1 5 1
2 3 1
2 5 1
3 4 1
3 5 1

样例输出 1

2 2 0 1 1

样例输入 2

2
5 6
1 2 1
1 5 1
2 3 1
2 5 1
3 4 1
3 5 1
3 3 1 2 2

样例输出 2

YES

样例解释

当初始点权与样例输出 1 中构造的一致时, 可以发现依次操作 3, 5, 4, 2, 3, 4, 1, 5, 2, 1 号点后, 所有点的点权与初始情况一致, 且这些操作均合法, 故可以进行无限次合法的收集操作.

容易注意到, 样例输入 2 给出的点权为样例输出 1 中构造的点权 +1, 故显然合法.

提示

在下发文件中含有 checker.exe (linux 格式下为 checker), 你可以使用它来验证你的输出是否正确. 具体的使用方式为 checker collect.in collect.out collect.out, 其中 collect.in 和 collect.out 为与 checker.exe 在相同目录下的输入输出文件.

限制与约定

对于所有数据, $o \in \{1, 2\}$, $1 \le n \le 3 \times 10^5$, $0 \le m \le \min\left(10^6, \frac{1}{2}n(n-1)\right)$, $1 \le i < j \le n$, $(i, j)$ 互不相同, $1 \le v \le 10^9$, $0 \le w'_i \le 10^{18}$.

注意在某些数据点中, 只考虑边权非 0 的边的情况下, 图可能不连通.