Shortest Path in a Directed Graph

Given a directed graph with \(n\) nodes and \(m\) edges, find the shortest path from node 1 to every other node.

The graph may contain multiple edges and self-loops. It is guaranteed that the graph does not contain any negative cycles.

Note: If a node is unreachable from node 1, output -1 for that node.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of nodes and edges respectively.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) describing a directed edge from node \(u\) to node \(v\) with weight \(w\). The graph might have self-loops and multiple edges between two nodes.

outputFormat

Output a single line with \(n\) space-separated integers. The \(i\)-th integer should be the shortest distance from node 1 to node \(i\). If node \(i\) is unreachable from node 1, output -1 for that node.

sample

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

0 2 3 4 5