Shortest Path Using Dijkstra's Algorithm

You are given a directed weighted graph with N nodes and M edges. Your task is to compute the shortest distance from a given source node S to all other nodes using Dijkstra's algorithm. If a node is not reachable from S, output INF for that node.

The distance update condition in the algorithm follows the formula: $$d[v] > d[u] + w$$, where d[u] is the current distance to node u and w is the weight of edge from u to v.

Note: The graph is 1-indexed. Read the input from standard input and output the result to standard output.

inputFormat

The first line contains two integers N and M representing the number of nodes and edges respectively. Each of the next M lines contains three integers u, v, and w representing an edge from node u to node v with weight w. The last line contains a single integer S, the source node.

outputFormat

Output a single line containing N space-separated values, where the i-th value is the minimum distance from node S to node i. If node i is unreachable, output INF for that node.

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

0 2 3 9 6