Minimum Delivery Time

You are given a graph with $N$ cities and $M$ bidirectional roads. Each road is represented as a triplet \( (u, v, w) \), where \( w \) is the time required to travel between city \( u \) and city \( v \). You will then be given $Q$ queries. For each query, you need to compute the minimum travel time from city \( C_1 \) to city \( C_2 \) using Dijkstra's algorithm. If there is no available route, output \(-1\).

Note: The roads may contain multiple connections between the same cities. In such cases, only the road with the smallest travel time should be considered.

inputFormat

The input is given via stdin and has the following format:

N M
u1 v1 w1
u2 v2 w2
... (M lines total)
Q
C1_1 C2_1
C1_2 C2_2
... (Q lines total)

Where:

• N is the number of cities.
• M is the number of roads.
• Each road is described by three integers \( u, v, w \) meaning there is a bidirectional road between city \( u \) and city \( v \) with travel time \( w \).
• Q is the number of queries.
• Each query consists of two integers \( C_1 \) and \( C_2 \), and you must compute the minimum delivery time from \( C_1 \) to \( C_2 \).

outputFormat

For each query, output a single line (via stdout) containing the minimum delivery time between the given cities. If no route exists, output \(-1\).

## sample

5 6
1 2 2
2 4 1
1 3 4
3 4 3
2 3 2
4 5 2
3
1 5
2 3
3 5

5
2
5

</p>