Taco Light Transmission

You are given a palace consisting of n crystals (nodes) and m bidirectional transmission lines (edges). Each transmission line connects two crystals and has a positive length.

Starting from the source crystal s, your task is to compute the shortest time for light to reach every crystal in the palace. If a crystal is unreachable, output -1 for that crystal.

The shortest path computation is based on the following formula in LaTeX format:

$$d_u = \min(d_u,\; d_v + w)$$

where \(d_v\) is the distance to a neighboring crystal and \(w\) is the length of the transmission line connecting them.

inputFormat

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

1. The first line contains three space-separated integers: n (the number of crystals), m (the number of transmission lines), and s (the starting crystal).
2. Each of the next m lines contains three space-separated integers u, v, and w, where u and v are the crystals connected by a transmission line and w is its length.

outputFormat

Output to standard output (stdout) exactly n lines. The i-th line should contain the shortest time from the starting crystal s to crystal i. If crystal i is unreachable, output -1 for that crystal.

## sample

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

0
3
2
8
10

</p>