Shortest Paths in a Directed Graph

You are given a directed weighted graph with n nodes and m edges. Your task is to compute the shortest path distances from a specified source node s to every other node in the graph. If a node is not reachable from the source, output -1 for that node.

You are required to implement Dijkstra's algorithm. The shortest distance d(v) for each node v is defined as:

$$ d(v)=\min_{\text{path } s \rightarrow v}\sum_{e \in \text{path}} w(e) $$

where w(e) is the weight of edge e along the path from s to v.

inputFormat

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

• The first line contains two integers n and m, representing the number of nodes and edges.
• The next m lines each contain three integers u, v, and w, indicating there is an edge from node u to node v with weight w.
• The last line contains a single integer s, the source node.

outputFormat

The output should be written to standard output (stdout) as a single line containing n space-separated integers. The i-th integer denotes the shortest distance from node s to node i. If node i is not reachable from s, output -1 instead.## sample

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

0 2 3 10 12