Shortest Path Computation

This problem requires you to compute the shortest path from a given source node to all other nodes in a weighted directed graph using Dijkstra's algorithm. The weight of an edge between nodes u and v is denoted by w and is assumed to be non-negative. Formally, if there is an edge from u to v with weight w, then the cost to travel from u to v is given by $$w$$. If a node is unreachable from the source, output -1 for that node.

Your task is to output the distance from the source node to every other node in the graph in a single line, separated by spaces.

inputFormat

The first line of input contains three integers N, M, and S representing the number of nodes, the number of edges, and the starting node respectively.

Each of the following M lines contains three integers u, v, and w representing an edge from node u to node v with weight w.

Note: The nodes are labeled from 1 to N.

outputFormat

Output a single line containing N integers. The i-th integer should represent the shortest distance from the source node S to node i. If node i is not reachable, output -1 instead.

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

0 2 3 9 6