P5960 [Template] Difference Constraints

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.

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 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`.

**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