Shortest Travel Time

You are given a directed graph with N nodes and M edges. Each edge from node u to node v has an associated travel time w. The graph does not contain cycles (i.e. it is unidirectional and acyclic). Your task is to determine the shortest travel time from a given starting station to a destination station.

If there is no valid route from the start to the destination, output -1.

Note: Use Dijkstra’s algorithm to solve the problem.

The formula for the shortest path to station i can be summarized as:

\( d[i] = \min_{(u,i) \in E} (d[u] + w(u,i)) \)

inputFormat

The input begins with an integer T (the number of test cases) on a new line. For each test case:

1. The first line contains two integers N and M: the number of stations and the number of edges.
2. The next M lines each contain three integers u v w representing an edge from station u to station v with a travel time of w.
3. The final line of the test case contains two integers representing the start and destination stations.

All input is provided via standard input (stdin). Ensure that you handle multiple test cases.

outputFormat

For each test case, output a single integer: the minimum travel time from the start to the destination station. If there is no valid path, output -1. The results for multiple test cases should each be printed on a new line to standard output (stdout).## sample

2
4 4
1 2 5
2 3 10
1 3 15
3 4 5
1 4
3 2
1 2 1
2 3 2
1 3

20
3