Wormhole Travel

You are given a network of n space stations connected by m wormholes. Each wormhole is a one‐way portal that allows travel from one station to another in a given amount of time. Your task is to compute the shortest time required to travel from a designated start station s to every other station. If a station is unreachable, output -1 for that station.

The problem can be modeled as a directed and weighted graph. Use Dijkstra's algorithm to find the minimum travel times efficiently. Remember that the stations are numbered from 1 to n, and the wormholes are given as triples \( (u, v, t) \) representing an edge from station \( u \) to station \( v \) with travel time \( t \).

Input/Output: The input is read from standard input, and the result should be printed to standard output, with the shortest times separated by spaces.

inputFormat

The first line contains three integers \( n \), \( m \), and \( s \), where \( n \) is the number of stations, \( m \) is the number of wormholes, and \( s \) is the starting station.

The next \( m \) lines each contain three integers \( u \), \( v \), and \( t \). Each line represents a wormhole from station \( u \) to station \( v \) with travel time \( t \).

outputFormat

Print a single line with \( n \) space-separated integers. The \( i^{th} \) integer represents the shortest travel time from station \( s \) to station \( i \). If station \( i \) is unreachable from \( s \), output -1 in its place.

5 6 1
1 2 3
1 3 1
2 4 2
3 2 1
3 4 5
4 5 1

0 2 1 4 5