题目描述

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

这种要求就可以用$\red {M（5≤M≤5000）}$个不等式表示，不等式形如$\red {t _i~ -t _j~ ≤B}$代表$\red {i}$和$\red {j}$的起始时间必须满足的条件。每个不等式的右边都是一个常数$\red {B}$，这些常数可能不相同，但是它们都在区间$\red {(-100,100)}$内。

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

输入格式

第一行是用空格隔开的两个正整数$\red {N}$和$\red {M}$，下面的$\red {M}$行每行有三个用空格隔开的整数$\red {i，j，B}$对应着不等式$\red {t _i~ -t _j~ ≤B}$。

输出格式

如果有可行的方案，那么输出$\red {N}$行，每行都有一个非负整数且至少有一个为$\red {0}$，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息NO SO-LUTION。

样例

输入样例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

2

5

4

1

输入样例2

5 5

1 2 -3

1 5 -1

2 5 -1

5 1 -5

4 1 4

输出样例2

NO SO-LUTION