DAG Shortest Paths

Given a directed acyclic graph (DAG) with \(n\) vertices and \(m\) trails, compute the shortest distance from the base vertex (vertex 0) to every other vertex. For each edge from vertex \(u\) to vertex \(v\) with length \(l\), update the distance using the formula: \(d[v] = \min(d[v], d[u] + l)\). If a vertex is unreachable from the base, output -1 for that vertex.

The vertices are numbered from 0 to \(n-1\). It is guaranteed that the graph is acyclic, meaning a topological order exists. Use an appropriate algorithm (such as topological sorting) to solve the problem efficiently.

inputFormat

The input is given via standard input. The first line contains two integers (n) and (m), where (n) is the number of vertices and (m) is the number of trails. Each of the following (m) lines contains three integers (u), (v) and (l), indicating that there is a directed edge (trail) from vertex (u) to vertex (v) with length (l).

outputFormat

Output a single line via standard output containing (n) space-separated integers. The (i)th integer should be the shortest distance from vertex 0 to vertex (i). If vertex (i) is unreachable, output -1 for that vertex.## sample

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

0 2 3 6 7