Dijkstra's Shortest Paths in an Undirected Graph

You are given an undirected weighted graph with N nodes and M edges. Each edge connects two distinct nodes with a non-negative weight. Your task is to compute the shortest distance from a given start node S to every other node using Dijkstra's algorithm.

If a node is not reachable from S, output -1 as its distance. The answer should be output as a list of N space-separated numbers, where the i-th number denotes the shortest distance from S to node i (nodes are numbered from 1 to N).

The mathematical formulation of the problem is as follows: Given a graph \(G=(V,E)\) with \(|V|=N\) and non-negative weights \(w(u,v)\) on each edge \((u,v) \in E\), find the distance array \(d[1\dots N]\) such that \[ d[i]=\begin{cases} 0, & i = S,\\ \min_{\text{path } S \to i} \sum_{(u,v)\in \text{path}} w(u,v), & \text{if node } i \text{ is reachable}, \\ -1, & \text{otherwise.} \end{cases} \]

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.

The following M lines each contain three integers u v w, indicating that there is an edge between nodes u and v with weight w. The graph is undirected, so each edge applies in both directions.

outputFormat

Output a single line containing N space-separated integers. The i-th integer should be the shortest distance from node S to node i. If a node is unreachable from S, print -1 instead of its distance.

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

0 5 3 6