P1260 Project Planning

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$.

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$.

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`.

SPJ provided by @zhouyonglong. Translated by ChatGPT 5