#969. 【模板】差分约束

【模板】差分约束

题目描述

给出一组包含 mm 个不等式,有 nn 个未知数的形如:

$$\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}$$

的不等式组,求任意一组满足这个不等式组的解。

输入格式

第一行为两个正整数 n,mn,m,代表未知数的数量和不等式的数量。

接下来 mm 行,每行包含三个整数 c,c′,yc,c',y,代表一个不等式 xc−xc′≤yx_c-x_{c'}\leq y。

输出格式

一行,nn 个数,表示 x1,x2⋯xnx_1 , x_2 \cdots x_n 的一组可行解,如果有多组解,请输出任意一组,无解请输出 NO。

样例

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

题目来源:洛谷 P5960