Shortest Path in an Undirected Weighted Graph

You are given an undirected weighted graph with \(N\) nodes and \(M\) edges. Each edge connects two nodes and has a non-negative weight. Your task is to compute the distances of the shortest paths from node 1 to all other nodes (i.e. nodes 2 through \(N\)).

If a node is unreachable from node 1, output \(-1\) for that node.

Note: The graph is undirected, which means that if there is an edge between nodes \(u\) and \(v\) with weight \(w\), then \(u\) is connected to \(v\) and \(v\) is connected to \(u\) with the same weight \(w\).

The problem can be solved using Dijkstra's algorithm. The time complexity of Dijkstra's algorithm using a priority queue is \(O((N + M) \log N)\).

inputFormat

The input is given via stdin in the following format:

N M
u1 v1 w1
u2 v2 w2
... 
uM vM wM

\(N\) is the number of nodes and \(M\) is the number of edges. Each of the next \(M\) lines contains three integers \(u\), \(v\) and \(w\) representing an edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output the shortest distances from node 1 to every other node (from node 2 to node \(N\)) in one line, separated by a space, via stdout.

If node i is not reachable from node 1, output \(-1\) at that position. If \(N = 1\), output an empty line.

## sample

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

1 3 6 7