Minimum Travel Times in a Bus Network

You are given a bus network with n bus stops and m bidirectional routes. Each route connects two bus stops and has an associated travel time. Your task is to compute the shortest travel times from a given starting bus stop to all other bus stops. If a bus stop is not reachable, output INF.

The problem can be formulated using Dijkstra's algorithm. In mathematical terms, if we denote the current best known travel time to vertex v as \(d(v)\) and an edge from u to v with weight \(w\), then the relaxation step is:

[ d(v) = \min\Big(d(v), ; d(u) + w\Big) ]

Read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The first line of input consists of three integers: n (the number of bus stops), m (the number of bus routes), and start (the starting bus stop).

The next m lines each contain three integers u, v, and w, indicating that there is a bidirectional bus route between bus stops u and v with travel time w.

outputFormat

Output a single line containing n values, where the i-th value represents the shortest travel time from the starting bus stop to bus stop i. If a bus stop is unreachable, output INF in its place. The values should be separated by spaces.

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

0 3 2 7