Shortest Path in a Directed Network

You are given a directed network with N nodes and M weighted edges. Your task is to determine the shortest path from a given starting node to every other node in the network. If a node is not reachable, output -1 for that node.

The network is represented as follows:

• N: Number of nodes (nodes are numbered from 0 to N-1).
• M: Number of directed edges.
• Each edge is given as three integers u, v, w which represents a directed edge from node u to node v with a weight w.
• start: The starting node from which the shortest path is calculated.

The shortest path problem is formulated using Dijkstra's algorithm. In mathematical form, if we denote the shortest distance from the start node to a node i as \(d(i)\), then:

[ \begin{aligned} d(start) &= 0, \ d(i) &= \min_{\text{edge } (j \to i)}{ d(j) + w_{ji} } \quad \text{for } i \neq start, \ \text{if } i \text{ is not reachable, then } d(i) &= -1. \end{aligned} ]

Your program should read input from stdin and output the result to stdout.

inputFormat

The first line contains two integers N and M, separated by a space.

The next M lines each contain three integers u, v, and w, representing a directed edge from node u to node v with weight w.

The last line contains one integer start, which is the starting node.

outputFormat

Output a single line containing N integers separated by spaces. The i-th integer denotes the shortest distance from the start node to node i. If node i is not reachable, output -1 for that node.

## sample

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

0 2 3 9 6