Minimum Travel Cost

You are given a weighted undirected graph representing a network of cities and roads. Each road has an associated cost. Your task is to compute the minimum travel cost from a starting city (A) to a destination city (B). The cost along a path is calculated as the sum of the costs of the roads taken. Formally, if (P) is a path from (A) to (B), the total cost is given by $$\sum_{e \in P} cost(e)$$. If there is no valid path from (A) to (B), output (-1).

This problem requires you to implement an efficient shortest path algorithm (such as Dijkstra's algorithm) and handle multiple test cases using standard input and output.

inputFormat

The first line contains an integer (T) representing the number of test cases. Each test case is described as follows:

• The first line contains two integers \(N\) and \(M\), representing the number of cities and the number of roads respectively.
• The next \(M\) lines each contain three integers \(U\), \(V\), and \(C\) indicating that there is an undirected road between city \(U\) and city \(V\) with a cost of \(C\).
• The last line of the test case contains two integers \(A\) and \(B\) denoting the starting city and the destination city.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum travel cost from city (A) to city (B), or (-1) if no such path exists. The output should be written to standard output (stdout).## sample

2
4 4
1 2 10
2 3 20
1 3 30
2 4 50
1 4
3 2
1 2 5
2 3 10
1 3

60
15

</p>