Shortest Path Queries

You are given an undirected graph with N nodes and M edges. Each edge has a non-negative weight. After the graph description, you are given T queries. Each query consists of two nodes, and your task is to compute the shortest path from the first node to the second node using the sum of edge weights. If there is no path between the nodes, output -1. The problem requires you to use Dijkstra's algorithm or any efficient shortest path algorithm.

The input and output are handled through standard input (stdin) and standard output (stdout). All formulas in this text are given in LaTeX format, for example: the weight of a path is defined as \( \text{weight}(P) = \sum_{e \in P} w(e) \).

inputFormat

The input is given from standard input and has the following format:

N M T
u1 v1 w1
u2 v2 w2
... (M lines)
q1_a q1_b
q2_a q2_b
... (T lines)

Here, the first line contains three integers: the number of nodes N, the number of edges M, and the number of queries T. Each of the next M lines contains three integers u, v, w, representing an undirected edge between nodes u and v with weight w. The following T lines each contain two integers A and B, representing a query asking for the shortest path from node A to node B.

outputFormat

For each query, output a single line containing the shortest path weight. If there is no valid path between the queried nodes, output -1.

## sample

5 6 3
1 2 5
2 3 2
3 4 1
4 5 4
1 3 9
2 5 7
1 5
1 4
3 5

12
8
5

</p>