Time Machine

Time limit1sMemory limit256 MB

Summary

Compute the fastest times from city 1 over bus routes with possibly negative durations, or print -1 when a reachable negative cycle exists.

Level: Medium4 of 10
Topics: Shortest path, Graph
Solved: No attempts yet

Problem

There are $N$ cities and $M$ bus routes, each running from one city to another. A route is written as three integers $A$ , $B$ , $C$ , where $A$ is the departure city, $B$ is the arrival city, and $C$ is the time the ride takes.

The time $C$ is not always positive. When $C = 0$ the ride is instant, and when $C < 0$ the bus is a time machine that sends you back in time.

Write a program that finds the fastest time to travel from city 1 to every other city.

Input

The first line has the number of cities $N$ ( $1 \le N \le 500$ ) and the number of bus routes $M$ ( $1 \le M \le 6000$ ).

Each of the next $M$ lines has one route $A$ , $B$ , $C$ ( $1 \le A, B \le N$ , $-10000 \le C \le 10000$ ). Several routes may connect the same pair of cities, and a route with $A = B$ may appear.

Output

If a trip that starts at city 1 can push the time back without bound, print -1 on the first line.

Otherwise print $N - 1$ lines holding the fastest time from city 1 to city 2, city 3, ..., city $N$ , one time per line in that order. If a city has no route from city 1, print -1 on its line. When $N = 1$ , print nothing.

Examples3

Example 1
Input
```
3 4
1 2 4
1 3 3
2 3 -1
3 1 -2
```
Expected output
```
4
3
```
Example 2
Input
```
3 4
1 2 4
1 3 3
2 3 -4
3 1 -2
```
Expected output
```
-1
```
Example 3
Input
```
3 2
1 2 4
1 2 3
```
Expected output
```
3
-1
```