Shortest Path in a Directed Graph

You are given a directed graph with (n) nodes and (m) weighted edges. Your task is to compute the shortest path from a given starting node (s) to every other node using Dijkstra's algorithm. If a node is not reachable from (s), output (-1) for that node. The optimization problem can be defined as follows:

[ d(v)=\min_{\text{paths from } s \text{ to } v} \sum_{(u,v)\in \text{path}} w(u,v) ]

Input and output formats are described below. Make sure your solution reads from standard input and writes to standard output.

inputFormat

The input starts with a line containing two integers (n) and (m), the number of nodes and edges respectively. This is followed by (m) lines, each containing three integers (u), (v), and (w), representing a directed edge from node (u) to node (v) with weight (w). The last line contains the starting node (s).

outputFormat

Output a single line containing (n) space-separated integers, where the (i)-th integer represents the shortest distance from node (s) to node (i). If a node is unreachable, output (-1) for that node.## sample

5 7
1 2 10
1 3 5
2 3 2
3 2 3
2 4 1
3 4 9
4 5 4
1

0 8 5 9 13