Shortest Paths in a Network of Attractions

You are given a city map where attractions are represented as nodes and the paths connecting them as directed edges with travel times. For each test case, your task is to compute the minimum travel time from a given starting attraction to every other attraction using Dijkstra's algorithm. If a particular attraction is unreachable from the starting point, output INF for that node.

The relaxation process follows the formula: $$d[v] = \min(d[v], d[u] + w)$$ where (d[u]) is the distance to node (u) and (w) is the weight of the edge from (u) to (v).

Read the input from standard input (stdin) and output the results to standard output (stdout) as specified.

inputFormat

The first line of the input contains an integer (t) (the number of test cases). For each test case, the first line contains two integers (n) and (m), where (n) is the number of attractions (nodes) and (m) is the number of paths (edges). The following (m) lines each contain three integers (u), (v), and (w), indicating a directed edge from node (u) to node (v) with weight (w). The last line of each test case contains an integer (s), the starting attraction.

outputFormat

For each test case, output a single line containing (n) space-separated values, where the (i)th value represents the minimum travel time from the starting attraction to attraction (i). If an attraction is unreachable, print INF instead of the travel time.## sample

2
4 4
0 1 1
0 2 4
1 2 2
2 3 1
0
3 3
0 1 2
1 2 3
0 2 5
1

0 1 3 4
INF 0 3