题目背景

人面不知何处去，桃花依旧笑春风。

题目描述

给定一张 $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
5 6
1 2 1
1 5 1
2 3 1
2 5 1
3 4 1
3 5 1

2 2 0 1 1

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

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 在相同目录下的输入输出文件。

返回值	信息
0	输出正确
1	你构造的方案中 $\sum w'_i$ 比正确的更小
2	你构造的方案中 $\sum w'_i$ 比正确的更大
3	你构造的方案不是 收集-free 的
4	你输出了 YES 和 NO 以外的字符串
5	你对于是否 收集-free 的判断错误

限制与约定

对于所有数据，$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 的边的情况下，图可能不连通。

Subtask 编号	$n$ 的上界	$m$ 的上界	特殊性质	分值
1	$10$	$20$	无特殊性质	$10$
2	$20$	$100$	^
3	$300$	$2000$
4	$3\times 10^5$	$n - 1$	$o = 1$，非 $0$ 边构成一棵树
5	^	$\min\left(10^6, \frac{1}{2}n(n-1)\right)$	$o = 1$	$30$
6		^	$o = 2$	$20$
7			无特殊性质	$10$