Efficient Message Transmission

You are given a network of N servers and M undirected communication links. Each link connects two servers u and v with a transmission time w. Given a starting server S, your task is to compute the shortest time required to send a message from S to every other server in the network.

If the message cannot reach a particular server, output UNREACHABLE for that server.

The problem can be mathematically stated as follows: For each server i (where 1 \leq i \leq N), find the minimum distance \(d_i\) from server S using the relation:

[ d_i = \min_{\text{paths } S \to i} \sum_{(u,v) \in \text{path}} w_{uv} ]

If \(d_i = \infty\), then the server is unreachable from S.

This problem is a classic application of Dijkstra's algorithm.

inputFormat

The first line of input contains three space-separated integers: N (the number of servers), M (the number of links), and S (the starting server).

The next M lines each contain three space-separated integers: u, v, and w, representing an undirected link between servers u and v with a transmission time of w.

Note: The server indices are 1-indexed.

outputFormat

Output N lines. The i-th line should contain the shortest time required to send a message from server S to server i. If server i is unreachable from S, output UNREACHABLE instead.

## sample

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

0
2
3
6
5

</p>