Dijkstra Shortest Paths

You are given a directed graph with n vertices and m edges. Each edge has a positive integer weight. Your task is to compute the shortest path from a given source vertex s to every other vertex using Dijkstra's algorithm. If a vertex is unreachable from s, output -1 for that vertex.

The problem can be formulated as follows: Given a graph \(G=(V, E)\) with \(V=\{1,2,\dots,n\}\) and a set of edges \(E\) where each edge is represented by a tuple \((u,v,w)\) with a positive weight \(w > 0\), find the shortest distance \(d(s,v)\) for all \(v \in V\) from the source vertex \(s\). Use the following input and output formats.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\), representing the number of vertices and edges, respectively. The next \(m\) lines each contain three space-separated integers \(u\), \(v\), and \(w\), representing a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\). The last line contains a single integer \(s\), the source vertex.

outputFormat

Output a single line with \(n\) space-separated integers, where the \(i\)-th integer represents the shortest distance from vertex \(s\) to vertex \(i\). If there is no path to vertex \(i\), print -1 instead.

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

0 2 3 6 7