Shortest Paths from Headquarters

You are given a city with n intersections and m roads. Each road connects two intersections and has an associated travel time. The roads are bidirectional. Your task is to compute the shortest travel time from the headquarters (located at intersection k) to every other intersection.

Use Dijkstra's algorithm to solve this problem. For each intersection i, you need to determine the minimum travel time d(i) from the headquarters such that

$$d(i)=\min \{\text{travel time along any valid path from } k \text{ to } i\} $$

If an intersection is unreachable from the headquarters, output INF for that intersection.

inputFormat

The input is provided through stdin and is formatted as follows:

• The first line contains three integers: n m k, where n is the number of intersections, m is the number of roads, and k is the index of the headquarters (0-indexed).
• The next m lines each contain three integers: u v t indicating a road between intersections u and v with travel time t.

outputFormat

Output a single line to stdout containing n space-separated values. Each value represents the shortest travel time from the headquarters to the corresponding intersection. If an intersection is not reachable, output INF for that intersection.

## sample

5 6 0
0 1 2
1 2 4
0 2 5
2 3 6
1 4 10
3 4 1

0 2 5 11 12

</p>