Shortest Path in an Undirected Graph

You are given an undirected, weighted graph with n nodes and m edges. The nodes are numbered from 1 to n. Each edge connects two nodes and has a positive weight.

Your task is to find the shortest path distance from a given starting node S to every other node in the graph. If a node is unreachable from S, output -1 for that node.

The shortest path distance from node S to a node i is defined as:

\(d(S,i)=\min_{\text{path } P:\,S\to i}\sum_{e\in P}w(e)\)

where \(w(e)\) is the weight of edge \(e\).

Read the graph details from the standard input and output the result to standard output.

inputFormat

The first line contains two integers n and m -- the number of nodes and the number of edges respectively.

Each of the next m lines contains three integers u, v and w, representing an undirected edge between nodes u and v with weight w.

The last line contains a single integer S, the starting node.

outputFormat

Output a single line containing n integers, where the i-th integer is the shortest distance from node S to node i. If node i is unreachable from S, print -1 instead of the distance.

Note: The distance for the starting node S should be 0.

## sample

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

0 2 3 6 7