Shortest Path in a Directed Acyclic Graph

Given a directed acyclic graph (DAG) with \(N\) vertices numbered from 1 to \(N\) and \(M\) edges, and a source vertex \(S\), compute the shortest path distance from \(S\) to every vertex in the graph. If a vertex is not reachable from \(S\), output \(-1\) for that vertex.

The graph is provided as a list of edges where each edge is represented by three integers \(u, v, w\) corresponding to a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\). It is guaranteed that the graph is acyclic, which enables the use of topological sorting for computing shortest paths efficiently.

Note: You should read the input from stdin and output your result to stdout.

inputFormat

The first line contains three integers \(N\), \(M\), and \(S\):

• \(N\): the number of vertices
• \(M\): the number of edges
• \(S\): the source vertex

The following \(M\) lines each contain three integers \(u\), \(v\), and \(w\) representing a directed edge from \(u\) to \(v\) with weight \(w\).

outputFormat

Output a single line containing \(N\) space-separated integers. The \(i\)-th integer represents the shortest path distance from the source vertex \(S\) to vertex \(i\). If a vertex is not reachable, print \(-1\) for that vertex.

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

0 2 3 9 6