Shortest Paths from Node 1

You are given an undirected weighted graph \(G=(V,E)\) with \(n\) nodes and \(m\) edges. The graph may be disconnected, and some nodes might not be reachable from node 1. Your task is to compute the shortest distance from node 1 to every other node. If a node is unreachable, output \(-1\) for that node.

Input starts with two integers \(n\) and \(m\). Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\). Use Dijkstra's algorithm or any other efficient method to compute the shortest distances.

Note: The nodes are numbered from 1 to \(n\), and the distance from node 1 to itself is 0.

inputFormat

The first line contains two integers (n) and (m), representing the number of nodes and the number of edges respectively. Each of the next (m) lines contains three integers (u), (v), and (w) describing an edge connecting nodes (u) and (v) with weight (w).

outputFormat

Print a single line with (n) space-separated integers, where the (i)-th integer is the shortest distance from node 1 to node (i). If a node is unreachable, output -1 for that node.## sample

5 7
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
4 5 6

0 7 9 20 14