Building Construction Scheduling

You are given a large construction project consisting of ( n ) tasks (numbered ( 1,2,\ldots,n ); (5\le n\le 1000)). Each task ( i ) must start at a non-negative time ( T_i ). However, due to strict preconditions, there are ( m ) constraints ((5\le m\le 5000)) on the starting times. Each constraint is an inequality of the form [ T_i - T_j \le b, ] where ( b ) is a constant in the interval ((-100, 100)). For example, after excavation, the foundation must be laid immediately, or after concrete pouring, one must wait for some time before removing the formwork.

Your task is to determine a possible sequence of starting times ( T_1,T_2,\dots,T_n ) that satisfies all the constraints or determine that no solution exists. In the case where a solution exists, at least one of the tasks must start at time (0) (i.e. the earliest task starts at time 0, aligning with the project start time).

This problem can be modeled as a system of difference constraints and solved by methods such as the Bellman–Ford algorithm. Note that if a solution is found but some ( T_i ) are negative, you may add a constant offset to all ( T_i ) (which does not affect the validity of the difference constraints) so that at least one ( T_i = 0 ) and all others are non-negative.

inputFormat

The input begins with a line containing two integers ( n ) and ( m ). Each of the following ( m ) lines contains three integers ( i,j,b ) representing a constraint of the form ( T_i - T_j \le b ).

outputFormat

If a solution exists, output ( n ) non-negative integers representing ( T_1, T_2, \dots, T_n ) (separated by spaces) such that all the given constraints are satisfied and at least one value is 0. If no solution exists, output a single line containing the string “Impossible”.

sample

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

0 0 0 0 0