Shortest Path in an Undirected Graph

You are given a weighted undirected graph with \( N \) nodes and \( M \) edges. The nodes are numbered from 1 to \( N \). Each edge connects two distinct nodes with a given positive weight.

Your task is to compute the shortest distance from a given starting node \( S \) to every other node in the graph using Dijkstra's algorithm. If a node is unreachable from \( S \), output \(-1\) as its distance.

The update in Dijkstra's algorithm can be formulated as:

[ \text{if } d[u] + w < d[v]\text{, then } d[v] = d[u] + w ]

Read the input from stdin and output the result to stdout.

inputFormat

The first line contains two integers \( N \) and \( M \), representing the number of nodes and edges, respectively.

The following \( M \) lines each contain three integers u, v, and w, representing an edge between node u and node v with weight w.

The last line contains a single integer \( S \), the starting node.

outputFormat

Output a single line containing \( N \) space-separated integers. The \( i\)-th integer represents the minimum distance from \( S \) to node \( i \). If a node is unreachable, output \(-1\) for that node.

4 4
1 2 1
2 3 2
1 3 4
3 4 7
1

0 1 3 10