【模板】差分约束

题目描述

给定 $n$ 个未知数 $x_1,x_2,\ldots,x_n$ 和 $m$ 个不等式。每个不等式形如

请判断这组不等式是否有解。若有解，输出任意一组满足所有不等式的整数解。

输入格式

第一行包含两个正整数 $n,m$，分别表示未知数和不等式的数量。

接下来 $m$ 行，每行包含三个整数 $c,c',y$，表示不等式 $x_c-x_{c'}\le y$。

输出格式

若不存在可行解，输出一行 NO。

否则输出一行 $n$ 个整数，依次表示 $x_1,x_2,\ldots,x_n$ 的一组可行解。输出的每个整数必须在 32 位有符号整数范围内。

样例输入 1

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

样例输出 1

5 3 5

数据范围

对于全部数据：$1\le n,m\le 5\times10^3$，$-10^4\le y\le10^4$，$1\le c,c'\le n$，且 $c\ne c'$。