题面背景

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

题目描述

给定一张 $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 \geq v_{i, j}$。

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

你有两种任务。第一种，构造一组点权 $w_{i^{\prime}}^{\prime}$ 使得 $w_i^{\prime}$ 收集-free，且最小化 $\sum_i w_{i^{\prime}}^{\prime}$ 第二种，给定一组点权 $w_{i^{\prime}}^{\prime}$ ，你需要判断 $w_i^{\prime}$ 是否 收集-free。

输入格式

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

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

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

若 $o=2$ ，接下来有一行 $n$ 个非负整数 $w_i^{\prime}$ ，代表你需要判断是否 收集-free 的一组点权。

输出格式

若 $o=1$ ，输出一行 $n$ 个非负整数 $w_{i^{\prime}}^{\prime}$ ，代表你构造的点权。你应当保证 $0 \leq w_i^{\prime} \leq 10^{18}$。

若 $o=2$ ，输出一行 YES 或 NO，代表 $w_i^{\prime}$ 是否 收集-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

提示

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

数据范围

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

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