## Another Contest 9 Problem 3 - Sun & Moon

View as PDF

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

Problem types

The sun and the moon travel across the universe among different locations. There are 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 and wants to know the soonest time when an eclipse could be observed at each of the given locations.

#### Input Specification

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

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

#### Output Specification

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

#### Sample Input

3 3
1 3 1
1 3 2
2 2 1

#### Sample Output

2
-1
2