Shortest Path in Directed Graph

Given a directed graph with \(n\) vertices and \(m\) edges, find the shortest path length from vertex \(1\) to every other vertex. Note that the graph may contain multiple edges and self-loops. If a vertex is unreachable from vertex \(1\), output -1 for that vertex.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(0 \le m \le 10^6\)), representing the number of vertices and edges respectively. Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) (\(1 \le u, v \le n\), \(1 \le w \le 10^9\)), which denote a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\).

outputFormat

Output a single line with \(n\) space-separated integers, where the \(i\)-th integer represents the shortest distance from vertex \(1\) to vertex \(i\). If vertex \(i\) is unreachable, output -1 in its place.

sample

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

0 2 3 6