Problem Description

You are given a system of inequalities with $m$ inequalities and $n$ unknowns of the form:

$$\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}$$

Find any set of values that satisfies this system of inequalities.

Input Format

The first line contains two positive integers $n, m$, representing the number of unknowns and the number of inequalities.

The next $m$ lines each contain three integers $c, c', y$, representing an inequality $x_c - x_{c'} \leq y$.

Output Format

Output one line with $n$ numbers, representing a feasible solution $x_1, x_2 \cdots x_n$. If there are multiple solutions, output any one of them. If there is no solution, output NO.

3 3
1 2 3
2 3 -2
1 3 1

5 3 5

Hint

Sample Explanation

$\begin{cases}x_1-x_2\leq 3 \\ x_2 - x_3 \leq -2 \\ x_1 - x_3 \leq 1 \end{cases}$

One feasible solution is $x_1 = 5, x_2 = 3, x_3 = 5$.

$\begin{cases}5-3 = 2\leq 3 \\ 3 - 5 = -2 \leq -2 \\ 5 - 5 = 0\leq 1 \end{cases}$

Constraints

For $100\%$ of the testdata, $1\leq n,m \leq 5\times 10^3$, $-10^4\leq y\leq 10^4$, $1\leq c,c'\leq n$, and $c \neq c'$.

Scoring Policy

You will get points as long as your output satisfies the system of inequalities. Please make sure the numbers in your output are within the int range.

If there is no solution but your program outputs a solution, the SPJ will return There is no answer, but you gave it, and the result will be WA.
If there is no solution and your program outputs NO, the SPJ will return No answer, and the result will be AC.
If a solution exists but your output is incorrect, the SPJ will return Wrong answer, and the result will be WA.
If a solution exists and your output is correct, the SPJ will return The answer is correct, and the result will be AC.

Translated by ChatGPT 5