Teleportation Portals

You are given a set of cities and a series of bidirectional teleportation portals connecting them, with each portal having a travel cost. Your goal is to answer multiple queries asking for the minimum travel time between two given cities.

For each query, if there is a valid route from city A to city B using the portals, you are to output the minimum total cost. Otherwise, if no route exists, output \( -1 \).

The problem may include multiple test cases. In each test case, the first line contains a single integer \( T \) representing the number of test cases. Then, for each test case, the first line contains three integers \( N \) (the number of cities), \( M \) (the number of portals), and \( Q \) (the number of queries). The following \( M \) lines each contain three integers \( u \), \( v \), and \( w \) representing a portal connecting city \( u \) and city \( v \) with travel cost \( w \). Finally, the next \( Q \) lines each contain two integers \( A \) and \( B \) specifying a query: the minimum travel time from city \( A \) to city \( B \).

You may assume that the portals allow bidirectional travel.

inputFormat

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

T
N M Q
u1 v1 w1
... (M lines)
A1 B1
... (Q lines)
... (repeat the above block for each test case)

Where:

• \( T \) is the number of test cases.
• \( N \) is the number of cities.
• \( M \) is the number of portals.
• \( Q \) is the number of queries.
• Each portal is defined by two cities \( u, v \) and a travel cost \( w \).
• Each query consists of two integers \( A \) and \( B \).

outputFormat

For every query, output a single line containing the minimum travel time required to travel from city \( A \) to city \( B \). If no valid route exists, output \( -1 \).

## sample

1
5 6 2
1 2 10
1 3 20
2 3 30
3 4 5
4 5 2
3 5 15
1 5
2 4

27
35

</p>