差分约束系统

题目描述

给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

$$\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,m$，代表未知数的数量和不等式的数量。

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

保证$1\leq n,m \leq 5\times 10^3$，$-10^4\leq y\leq 10^4$，$1\leq c,c'\leq n$，$c \neq c'$。

输出格式

一行，$n$ 个数，表示 $x_1 , x_2 \cdots x_n$，无解请输出 -1。

样例输入

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

样例输出

0 0 2