Given an undirected complete graph $G$ with $n$ vertices. Each edge $(i,j)$ has a non-negative integer weight $v_{i,j}$, and it is guaranteed that $v_{i,i}=0$ and $v_{i,j}=v_{j,i}$.

At the same time, each vertex has a non-negative integer variable $w_i$.

Define one collect operation on a vertex $i$ as: add $\sum_j v_{i,j}$ to $w_i$, and subtract $v_{i,j}$ from $w_j$ for every $j$. A collect operation on vertex $i$ is called legal if and only if before the operation, $w_j \ge v_{i,j}$ holds.

A set of vertex weights is called collect-free on graph $G$ if and only if, starting from these vertex weights, there exists a way to perform infinitely many legal collect operations.

You have two tasks. The first is to construct a set of vertex weights $w'_i$ such that $w'_i$ is collect-free, and minimize $\sum_i w'_i$. The second is: given a set of vertex weights $w'_i$, you need to determine whether $w'_i$ is collect-free.

Input Format

The first line contains a positive integer $o$, indicating your task type.

The second line contains a positive integer $n$ and a non-negative integer $m$, indicating the number of vertices of $G$ and the number of edges whose weight is non-zero.

The next $m$ lines each contain three positive integers $i$, $j$, $v$, indicating that the edge between $i$ and $j$ has weight $v$.

If $o=2$, then the next line contains $n$ non-negative integers $w'_i$, representing the vertex weights you need to judge as collect-free or not.

Output Format

If $o=1$, output one line with $n$ non-negative integers $w'_i$, representing the vertex weights you construct. You should guarantee $0 \le w'_i \le 10^{18}$.

If $o=2$, output one line with YES or NO, indicating whether $w'_i$ is collect-free.

Example

Sample Input 1

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

Sample Output 1

2 2 0 1 1

Sample Input 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

Sample Output 2

YES

Explanation

When the initial vertex weights are the same as those constructed in Sample Output 1, one can observe that after performing operations on vertices $3, 5, 4, 2, 3, 4, 1, 5, 2, 1$ in order, all vertex weights return to the initial state, and all these operations are legal. Therefore, it is possible to perform infinitely many legal collect operations.

It is easy to notice that the vertex weights given in Sample Input 2 equal the constructed vertex weights in Sample Output 1 plus $1$, so they are obviously legal.

Notes

The attached package contains checker.exe (or checker on Linux). You can use it to verify whether your output is correct. The usage is checker collect.in collect.out collect.out, where collect.in and collect.out are the input and output files in the same directory as checker.exe.

Constraints

For all data, $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$, all $(i,j)$ are distinct, $1 \le v \le 10^9$, $0 \le w'_i \le 10^{18}$.

Note that in some test points, if we only consider edges with non-zero weight, the graph may be disconnected.