Shortest Paths from the Capital

In a fictional country, there are n cities connected by m one-way roads. City 1 is designated as the capital. Each road has a positive length. The government wants to determine the shortest possible distance from the capital to every other city. If a city is unreachable from the capital, report its distance as \( -1 \).

You are given the number of cities and roads, followed by a list of roads where each road is represented by three integers \( u \), \( v \), and \( w \) indicating there is a one-way road from city \( u \) to city \( v \) of length \( w \). Compute and output the shortest distances from city 1 to every other city using Dijkstra’s algorithm or any other efficient shortest path algorithm.

Note: The cities are numbered from 1 to n. For the capital (city 1), you do not need to output its distance.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• \( n \) is the number of cities.
• \( m \) is the number of one-way roads.
• Each of the next \( m \) lines contains three integers \( u \), \( v \), and \( w \) indicating a road from city \( u \) to city \( v \) with length \( w \).

outputFormat

Output a single line on standard output (stdout) containing \( n-1 \) space-separated integers. The \( i^{th} \) integer (for \( 2 \le i \le n \)) should represent the shortest distance from the capital (city 1) to city \( i \). If a particular city is unreachable, output \( -1 \) for that city. If \( n = 1 \), output an empty line.

5 7
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
3 4 2

2 3 5 6