Minimum Delivery Time

You are given a city road network with n junctions and m directed roads. Each road has an associated travel time. However, some roads are currently unavailable. For each test case, you are also given the starting junction s and the destination junction d. Your task is to compute the minimum time required to travel from s to d while avoiding the unavailable roads, or output -1 if no valid path exists.

The problem can be formulated as finding the shortest path in a weighted directed graph where certain edges are blocked. You may use Dijkstra's algorithm to solve this problem. In your solution, any formulas should be expressed in LaTeX format. For example, the update of the distance may be written as:

$$d[v] = \min(d[v], d[u]+w(u,v))$$

Be sure to read input from standard input and write output to standard output.

inputFormat

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

• The first line contains three integers n m u, where n is the number of junctions, m is the number of roads, and u is an extra parameter (unused in the computation).
• The next m lines each contain three integers u v t indicating there is a directed road from junction u to junction v with travel time t.
• The next line contains an integer k representing the number of unavailable roads.
• The following k lines each contain two integers a b representing that the road from a to b is unavailable.
• The last line of the test case contains two integers s d, the starting and destination junctions respectively.

All numbers are separated by spaces.

outputFormat

For each test case, output a single integer on a new line: the minimum delivery time from s to d considering the unavailable roads. If no path exists, output -1.

## sample

4
4 5 1
1 2 10
1 3 5
2 3 2
3 4 1
4 2 3
1
2 3
1 4
2 1 0
1 2 5
0
1 2
4 4 4
1 2 10
2 3 10
3 4 10
4 1 10
4
1 2
2 3
3 4
4 1
1 4
5 7 2
1 2 2
1 3 10
2 3 3
2 4 1
3 5 2
4 5 4
3 4 1
2
1 3
3 5
1 5

6
5
-1
7

</p>