P15110 Silent End

Some top coders in the computer lab are discussing a “code army”. grg feels too weak to join in, so he can only listen to their heated talk.

grg heard $m$ comments. The $i$-th one is in the form $(u_i, v_i, w_i)$, which are the commenter, the person being commented on, and the estimated rating. However, these comments may not be accurate. Specifically, if the commenter’s real rating is greater than or equal to the person being commented on, the commenter will underestimate them, making $w$ smaller than the real rating by $1$; if the commenter’s real rating is less than the person being commented on, the commenter will overestimate them, making $w$ larger than the real rating by $1$. Because this group is very close, **everyone is commented on at least once**. Now grg wants you to construct a set of ratings for these people such that all comments are satisfied. If it does not exist, report it.

The first line contains two positive integers $n, m$. The next $m$ lines each contain three non-negative integers $u_i, v_i, w_i$, with the meaning described above.

If there is no solution, output `NO`. Otherwise output `YES`, then output a line with $n$ integers representing the ratings you construct. You must ensure that the constructed ratings are within the range of signed 32-bit integers, otherwise it may fail randomly.

**This problem uses bundled testdata.** $\texttt{Subtask 1(30pts)}:$ $n \leq 20$, $m \leq 100$. $\texttt{Subtask 2(70pts)}:$ No additional constraints. For all testdata, $1 \le n \leq 5 \cdot 10^5$, $n \le m \leq 10^6$, $0 \leq w_i \leq 10^9$. **It is guaranteed that everyone is commented on at least once.** Translated by ChatGPT 5