Taco: Shortest Path Queries

You are given an undirected weighted graph with n nodes and m edges. Each edge connects two nodes and has an associated positive weight.

Your task is to answer q queries. In each query, given two nodes s and t, you should compute the minimum distance between them. If there is no path from s to t, output -1.

The shortest path distance between nodes s and t is defined as:

$$d(s,t)=\min\left\{\sum_{(u,v)\in P}w(u,v)\right\}$$

where \(P\) is any path connecting s and t and \(w(u,v)\) denotes the weight of the edge between nodes \(u\) and \(v\>.

You are required to use Dijkstra's algorithm (or any equivalent method) to solve the problem efficiently.

inputFormat

The first line contains three space-separated integers: n (the number of nodes), m (the number of edges), and q (the number of queries).

The next m lines each contain three integers u, v, and w, representing an undirected edge between nodes u and v with weight w.

The following q lines each contain two integers s and t, representing a query asking for the shortest path from node s to node t.

outputFormat

For each query, output a single integer on a new line representing the shortest path distance from s to t. If no path exists, output -1.

## sample

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

9
11
7

</p>