The sun and the moon travel across the universe among ~N~ different locations. There are ~M~ different bidirectional celestial paths that the sun and the moon can take to go between different locations. An eclipse is when the sun and the moon are both at the same location. The sun and the moon are constantly on the move along some celestial path as long as the location they are at has some celestial path incident to it.

Nick currently observes the sun at location 1 and the moon at location ~N~ and wants to know the soonest time when an eclipse could be observed at each of the ~N~ given locations.

Constraints

~2 \le N \le 10^5~

~1 \le M \le 10^5~

~1 \le a_i, b_i \le N~

~1 \le y_i \le 3~

Input Specification

The first line contains two space-separated positive integers, ~N~ and ~M~.

The next ~M~ lines contain three space-separated positive integers, ~a_i~, ~b_i~, and ~y_i~, indicating that there is a bidirectional celestial path from location ~a_i~ to location ~b_i~ that takes ~y_i~ years to traverse.

Output Specification

Output ~N~ lines. On the ~i~th line, output -1 if no eclipse can ever happen at that location. Otherwise, output a positive integer ~e_i~, the minimum number of years such that it is possible to see an eclipse at location ~i~ in ~e_i~ years.

Sample Input

3 3
1 3 1
1 3 2
2 2 1

Sample Output

2
-1
2