Shortest Path in a Weighted Undirected Graph

You are given a weighted undirected graph with n nodes and m edges. The weight on each edge is non-negative. For each test case, your task is to find the shortest path from a given starting node s to a target node t. If there is no possible path, output -1.

The problem can be formally stated as follows:

Given an integer $T$, the number of test cases. For each test case, the first line contains two integers $n$ and $m$. This is followed by $m$ lines, each containing three integers $u$, $v$, and $w$, representing an undirected edge between nodes $u$ and $v$ with a non-negative weight $w$. The last line of each test case contains two integers $s$ and $t$ indicating the starting and target nodes respectively. Your task is to compute the shortest distance from node $s$ to node $t$ using an efficient algorithm (e.g., Dijkstra's algorithm).

Note: The input is read from stdin and the output should be written to stdout.

inputFormat

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

1. The first line of a test case contains two space-separated integers: $n$ (number of nodes) and $m$ (number of edges).
2. The next $m$ lines each contain three space-separated integers $u$, $v$, and $w$, indicating there is an undirected edge between node $u$ and node $v$ with weight $w$.
3. The last line of the test case contains two space-separated integers $s$ and $t$, representing the starting and target nodes respectively.

All input is read from stdin.

outputFormat

For each test case, output a single line containing the shortest distance from node $s$ to node $t$. If there is no path between the nodes, output -1. The result for each test case should be printed on a new line on stdout.

## sample

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

3
12

</p>