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 i-th daughter is A_i, folllowing conditions should be satisfied:

• -10000≤ A_i≤ 10000
• A_N - A₁ 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: 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.

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