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 Xi, I promise to give you dowry not less than Ci burles more than to daughter Yi", 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 i-th daughter is Ai, folllowing conditions should be satisfied:
  • -10000≤ Ai≤ 10000
  • AN - A1 should be minimal

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: Xi, Yi, Ci (1≤ Xi, YiN; XiYi; 0≤ Ci≤ 1000). The youngest daughter has the number one, the oldest — N. Each pair Xi, Yi can appear in the input several times.

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.

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