Shortest Cable Lengths

Hard#graphs #dijkstra #shortest-path· solved by 0 · time limit 2.0 s

Junctions $1 \dots n$ are joined by $m$ cables (undirected) with positive lengths. Print the shortest distance from junction $s$ to every junction ( $-1$ if unreachable). Use Dijkstra's algorithm with a priority queue.

Input

$n$ and $m$ , $m$ lines u v length, then $s$ .

Output

$n$ distances on one line.

Constraints

$1 \le n \le 10^5$ , $0 \le m \le 2 \times 10^5$ , $1 \le$ length $\le 10^4$ — use 64-bit distances.

Sample 1

Input

Output

0 3 1 8