Problem Description

Building a large structure is a challenging project, consisting of $n$ sub-tasks, numbered $1, 2, \cdots, n$ where $5 \leq n \leq 1000$. The start times $T_1, T_2, \cdots, T_n$ for these tasks are not easily determined due to strict starting conditions for some tasks (but these start times are non-negative integers, as they must begin after the project starts). For example, excavation must be followed immediately by foundation laying; however, after concrete pouring, there is a waiting period before removing the formwork.

These requirements can be represented by $m$ inequalities, where $5 \leq m \leq 5000$. Each inequality is of the form $T_i - T_j \leq b$, indicating the condition that must be satisfied by the start times of tasks $i$ and $j$. The right-hand side of each inequality is a constant $b$, which may vary but is within the range $(-100, 100)$.

Your task is to write a program that, given such inequalities, finds a possible sequence of start times $T_1, T_2, \cdots, T_n$, or determines if there is no solution. In case of a solution, ensure that at least one of the start times is $0$, meaning the earliest task starts at the same time as the entire project.

Input Format

The first line contains two integers $n$ and $m$ separated by spaces. The following $m$ lines each contain three integers $i, j, b$ corresponding to the inequality $T_i - T_j \leq b$.

Output Format

If a feasible solution exists, output $n$ lines, each containing a non-negative integer, with at least one being $0$, representing the start times of each task in order. If no feasible solution exists, output the message NO SOLUTION.

Sample Input and Output

Input Sample #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

Output Sample #1

0
2
5
4
1

Input Sample #2

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

Output Sample #2

NO SOLUTION

Notes

Special Judge provided by @zhouyonglong.

见题面 Input 部分

见题面 Output 部分