题目描述

建造一幢大楼是一项艰巨的工程。整个工程由 $n$ 个子任务构成，编号为 $1,2,\ldots,n$。由于一些任务的起始条件受到严格限制，各任务的起始时间 $T_1,T_2,\ldots,T_n$ 不容易确定。这些起始时间都是非负整数，因为所有任务都必须在整个工程开始后启动。

这些要求可以用 $m$ 个不等式表示。不等式 $T_i-T_j\le b$ 表示任务 $i$ 和任务 $j$ 的起始时间必须满足相应条件。

请找出一种可行的起始时间序列，或者判断问题无解。对于有解的情况，最早进行的任务必须与整个工程同时开始，即 $T_1,T_2,\ldots,T_n$ 中至少有一个为 $0$。

输入格式

第一行包含两个正整数 $n,m$。

接下来 $m$ 行，每行包含三个整数 $i,j,b$，表示不等式：

输出格式

如果存在可行方案，输出 $n$ 行，每行一个非负整数，依次表示 $T_1,T_2,\ldots,T_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 -1
5 4 -3

0
2
5
4
1

样例 #2

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

NO SOLUTION

数据范围与提示

• $5\le n\le1000$；
• $5\le m\le5000$；
• $-100<b<100$。

本题使用特殊评测。