Shortest Travel Time

You are given a network of N cities connected by M bidirectional roads. Each road has an associated travel time. One of these cities is designated as the Capital. Your task is to compute the shortest travel time from the Capital to every other city.

If a city is not reachable from the Capital, output -1 for that city. The travel times should be printed in order from city 1 to city N. Note that the graph may contain self-loops and disconnected components.

Algorithm Hint: Consider using Dijkstra's algorithm to compute the shortest distances efficiently. The formula for updating a neighbor's distance is given in \( \text{new distance} = \min(\text{current distance}, \text{current distance} + \text{edge weight}) \).

Input Constraints: The values of N and M can be assumed to be such that a solution using Dijkstra's algorithm will run efficiently.

inputFormat

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

N M Capital
u1 v1 t1
u2 v2 t2
... 
uM vM tM

where:

• N is the number of cities.
• M is the number of roads.
• Capital is the index of the city designated as the Capital.
• Each of the next M lines contains three integers u, v, and t representing a road between cities u and v with travel time t.

outputFormat

Output to standard output (stdout) a single line containing N space-separated integers, where the i-th integer is the shortest travel time from the Capital to city i. If a city cannot be reached, output -1 for that city.

## sample

4 4 1
1 2 5
1 3 10
2 4 15
3 4 10

0 5 10 20