Time Machine

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.

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.

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.