Description

Building a skyscraper is a challenging project composed of $n$ subtasks, numbered $1, 2, \cdots, n$ ($5 \le n \le 1000$). Due to strict constraints on the starting conditions of some tasks, the start times $T_1, T_2, \cdots, T_n$ are not easy to determine (however, these start times are all non-negative integers because they must start after the entire project begins). For example: after excavation is completed, the foundation must be laid immediately; but after concrete pouring is completed, one must wait for a while before removing the formwork.

Such requirements can be expressed by $m$ ($5 \le m \le 5000$) inequalities. An inequality of the form $T_i - T_j ≤ b$ represents a constraint that the start times of tasks $i$ and $j$ must satisfy. The right-hand side of each inequality is a constant $b$. These constants may differ, but they all lie within the interval $(-100, 100)$.

Your task is to write a program that, given inequalities like the above, finds a possible sequence of start times $T_1, T_2, \cdots, T_n$, or determines that the problem has no solution. For solvable cases, the earliest task must start at the same time as the entire project, that is, at least one of $T_1, T_2, \cdots, T_n$ equals $0$.

Input Format

The first line contains two positive integers $n$ and $m$ separated by a space. Each of the next $m$ lines contains three integers $i, j, b$ separated by spaces, corresponding to the inequality $T_i - T_j ≤ b$.

Output Format

If there is a feasible solution, output $n$ lines. Each line contains a non-negative integer, and at least one of them must be $0$, representing in order the start time of each task. If there is no feasible solution, output the message NO SOLUTION.

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

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

NO SOLUTION

Hint

SPJ provided by @zhouyonglong.

Translated by ChatGPT 5