Minimum Risk Levels

You are given a directed graph with N junctions and M edges. Each edge from node u to node v has an associated risk level w. After the graph description, you are provided Q queries. Each query consists of two integers a and b and asks for the minimum total risk level to travel from junction a to junction b. If no valid path exists between the two junctions, output -1.

This problem can be solved using Dijkstra's algorithm. The distances are initialized as $\infty$ (infinity) except for the starting junction where the distance is 0. For each query, run the algorithm to compute the minimum risk level path from the source to the destination.

inputFormat

The input is read from the standard input (stdin) and follows the format below:

T
N M
u1 v1 w1
u2 v2 w2
... (M lines)
Q
a1 b1
a2 b2
... (Q lines)

Where:

• T is the number of test cases.
• For each test case, N denotes the number of junctions and M is the number of directed edges.
• Each of the next M lines contains three integers u, v, and w which represent an edge from junction u to v with risk level w.
• Q is the number of queries.
• Each of the next Q lines contains two integers a and b indicating a query from junction a to junction b.

outputFormat

For each query, output a single line containing the minimum total risk level from node a to node b. If there is no path from a to b, output -1.

## sample

1
4 5
1 2 10
2 3 10
3 4 15
1 3 20
2 4 25
2
1 4
3 1

35
-1

</p>