Dijkstra's Shortest Path Challenge

Given an undirected weighted graph with \(n\) vertices and \(m\) edges, your task is to compute the shortest distance from vertex 1 to every other vertex. If a vertex is unreachable from vertex 1, output \(-1\) for that vertex.

The graph is described by \(m\) edges. Each edge is represented by a tuple \((u, v, w)\) indicating that there is an edge between vertices \(u\) and \(v\) with weight \(w\). All weights are positive integers. Use Dijkstra's algorithm to solve the problem.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively. The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), indicating an edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single line containing \(n\) integers separated by spaces. The \(i^{th}\) integer represents the shortest distance from vertex 1 to vertex \(i\). If vertex \(i\) is unreachable, output \(-1\).

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

0 1 2 3