Shortest Path in a Directed Acyclic Graph (DAG)

You are given a Directed Acyclic Graph (DAG) with N nodes and M weighted edges. Your task is to compute the shortest path from a given start node to every other node in the graph. If a node is unreachable, output \(\mathrm{INF}\) for that node.

The graph has no cycles, which allows the use of topological sorting to efficiently compute the shortest path distances. Formally, for each node \(v\), you must compute the distance \(d(v)\) such that:

[ d(v)=\min_{\text{paths from start to } v}\sum_{e \in path}w(e) ]

If there is no path from the start node to \(v\), then \(d(v)=\mathrm{INF}\).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer \(T\) denoting the number of test cases.
2. For each test case:
   1. The first line contains two integers \(N\) and \(M\), where \(N\) is the number of nodes and \(M\) is the number of edges.
   2. The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\) representing an edge from node \(u\) to node \(v\) with weight \(w\).
   3. The next line contains a single integer indicating the start node.

Note: The nodes are numbered from 1 to \(N\).

outputFormat

For each test case, output a single line containing \(N\) space-separated values. Each value represents the shortest distance from the start node to the corresponding node (from node 1 to node \(N\)). If a node is unreachable, output INF for that node.

## sample

6
5 6
1 2 2
1 3 6
2 4 3
2 5 4
3 4 2
4 5 1
1
4 4
1 2 1
2 3 2
1 3 4
3 4 3
1
4 4
1 2 1
1 3 4
2 3 3
3 4 2
1
6 9
1 2 1
1 3 5
2 3 2
2 4 6
3 4 2
3 5 3
4 5 1
4 6 7
5 6 2
1
3 3
1 2 5
2 3 10
1 3 15
1
4 2
1 2 1
3 4 1
1

0 2 6 5 6
0 1 3 6
0 1 4 6
0 1 3 5 6 8
0 5 15
0 1 INF INF

</p>