Shortest Guaranteed Path

You are given an undirected weighted graph with n nodes and m edges. Each edge has a non-negative weight. You will be given a number of queries, each asking for the shortest path distance between two nodes.

For each query, if there exists a path between the two nodes, output the total minimum weight; otherwise, output -1.

You can solve the problem using Dijkstra's algorithm. The distance update formula is given by:

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

inputFormat

The input is read from standard input (stdin) and has the following format:

T
for each test case:
    n m
    u1 v1 w1
    u2 v2 w2
    ...
    um vm wm
    q
    a1 b1
    a2 b2
    ...
    aq bq

Where:

• T is the number of test cases.
• n is the number of nodes and m is the number of edges.
• Each of the next m lines contains three integers u, v, and w representing an edge between nodes u and v with weight w.
• q is the number of queries.
• Each query consists of two integers a and b representing the start and end nodes.

outputFormat

For each test case, output one line containing q space-separated integers, where each integer is the shortest distance between the given pair of nodes. If there is no valid path, output -1 for that query.

## sample

1
5 6
1 2 10
1 3 3
2 3 1
2 4 2
3 5 6
4 5 7
3
1 5
2 5
1 4

9 7 6

</p>