Capital City Shortest Path

You are given a directed weighted graph representing a network of cities and roads. There are n cities numbered from 1 to n and m directed roads connecting them. Each road is described by the triple \( (u, v, w) \) meaning there is a road from city \( u \) to city \( v \) that takes w time to travel.

Your task is to compute the minimum travel time from a designated capital city S to every other city. If a city is unreachable from \( S \), output \(-1\) for that city.

The problem can be formally described as follows:

Given integers \( n, m, S \) and a list of \( m \) triples \( (u, v, w) \), compute an array \( d[1..n] \) where each \( d_i \) is defined as:

\[ d_i = \begin{cases} 0, & \text{if } i = S \\ \min\{\text{travel times from } S \text{ to } i\}, & \text{if a path exists} \\ -1, & \text{otherwise} \end{cases} \]

Use an efficient shortest path algorithm (e.g., Dijkstra's algorithm) to solve this problem.

inputFormat

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

1. The first line contains three integers \( n \), \( m \), and \( S \) where \( n \) is the number of cities, \( m \) is the number of roads, and \( S \) is the index of the capital city.
2. The next \( m \) lines each contain three integers \( u \), \( v \), and \( w \), representing a road from city \( u \) to city \( v \) with travel time \( w \).

Constraints guarantee that the input size is manageable by standard algorithms.

outputFormat

Output a single line to stdout containing \( n \) space-separated integers. The \( i\)-th integer should represent the minimum travel time from the capital city \( S \) to city \( i \). If city \( i \) is unreachable from \( S \), output \(-1\) instead.

## sample

4 4 1
1 2 1
2 3 2
3 4 1
4 2 3

0 1 3 4

</p>