Minimum Difficulty Route

In this problem, you are given one or more directed graphs representing attractions connected by passages with a certain difficulty level. For each test case, you will be provided with the number of rooms (nodes), the number of passages (directed edges), and a set of queries. Each passage is described by three integers u, v, w indicating a directed edge from room u to room v with difficulty w. For each query, you must determine the minimum total difficulty (the sum of weights) required to travel from a starting room to a destination room. If there is no valid route, output -1.

The shortest path is defined mathematically as: [ \text{minimize } \sum_{(u,v) \in P} w(u,v) \quad \text{subject to } P \text{ is a valid path from } s \text{ to } e. ] You are expected to implement an efficient solution (for example, using Dijkstra's algorithm).

inputFormat

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

• The first line contains an integer T, the number of test cases.
• For each test case, the first line contains three integers N, M, Q, where N is the number of rooms, M is the number of passages, and Q is the number of queries.
• The next M lines each contain three integers u, v, w, representing a directed passage from room u to room v with a difficulty of w.
• The next Q lines each contain two integers s and e, representing a query for the minimum difficulty route from room s to room e.

outputFormat

For each query, output the minimum total difficulty on a new line. If there is no valid route from s to e, output -1.## sample

1
4 4 2
1 2 5
2 3 1
3 4 2
1 3 10
1 4
3 2

8
-1