535. 工程规划

【问题描述】

造一幢大楼是一项艰巨的工程，它是由 $n$ 个子任务构成的，给它们分别编号$1,2,\cdots, n(5\leq n\leq 1000)$。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间 $T_1,T_2,\cdots,T_n$并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。

这种要求就可以用$m(5\leq m\leq 5000)$个不等式表示，不等式形如$T_i- T_j\leq b$代表$i$和$j$的起始时间必须满足的条件。每个不等式的右边都是一个常数 $b$ ，这些常数可能不相同，但是它们都在区间$(-100,100)$ 内。

你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列$T_1,T_2,\cdots,T_n$，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，$T_1,T_2,\cdots,T_n$中至少有一个为 0 。

【输入格式】

第一行是用空格隔开的两个正整数$n$和$m$。

接下来 $m$ 行每行有三个用空格隔开的整数 $i,j,b$对应着不等式$T_i- T_j\leq b$。

【输出格式】

如果有可行的方案，那么输出$n$行，每行都有一个非负整数且至少有一个为$0$，按顺序表示每个任务的起始时间。

如果没有可行的方案，就输出信息“NO SOLUTION”。

【输入样例1】

5 8
1 2 0
1 5 -1
2 5 1
3 1 5
4 1 4
4 3 -1
5 3 -3
5 4 -3

【输出样例1】

0
0
5
4
1

【输入样例2】

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

【输出样例2】

NO SOLUTION