298. King Berl VI
Time limit per test: 0.75
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
King Berl VI has
N daughters and no sons. During his long life he gave a number of promises to his daughters. All the promises have the following wording: "daughter
X_{i}, I promise to give you dowry not less than
C_{i} burles more than to daughter
Y_{i}", where
i represents the number of the promise. Before his death the king decided to give some amount of money to each daughter. As far as he was the fair king, he decided to fullfill all his promises. But he was not only fair but also very greedy, he decided that he can give negative amount of burles as a dowry (i.e. daughter should pay this amount of burles to the treasury). Because of his born greed and by advice of the minister of finances, he made a decision that absolute value of each dowry should not exceed 10000 burles and the difference between dowry of the oldest and of the youngest daughters should be as small as possible (note, this value can be negative).
I.e. if the dowry given to the
ith daughter is
A_{i}, folllowing conditions should be satisfied:
 10000≤ A_{i}≤ 10000
 A_{N}  A_{1} should be minimal
Input
The fist line of the input file contains two integers numbers
N and
M (2≤
N≤ 10000; 0≤
M≤ 100000), where
N is the number of daughters and
M is the number of promises. The following
M lines contain the description of promises in the following form:
X_{i},
Y_{i},
C_{i} (1≤
X_{i},
Y_{i}≤
N;
X_{i}≠
Y_{i}; 0≤
C_{i}≤ 1000). The youngest daughter has the number one, the oldest —
N. Each pair
X_{i},
Y_{i} can appear in the input several times.
Output
Write to the output number 1 if there is no solution for the problem (i.e. there is no sequence of
N integers which satisfies all described above requirements). Write to the output
N integer numbers — the amount of dowry of each daughter in burles, if solution exists. If there are several solutions output any of them.
Example(s)
sample input

sample output

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

3 2 1 3

sample input

sample output

2 2
1 2 0
2 1 0

7 7
