Another Contest 9 Problem 3 - Sun & Moon

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 256M

Problem types

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.


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 ith 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



There are no comments at the moment.