Shortest Path Queries

You are given an undirected weighted graph with n nodes and m edges. Your task is to answer q queries; each query consists of two nodes, and you must determine the shortest path distance between them. If no path exists between the queried nodes, output -1.

You are required to use Dijkstra's algorithm to solve the problem. In the algorithm, the formula for updating the distance is given by \(d[v]=\min(d[v], d[u]+w)\), where \(d[u]\) is the current shortest distance to node \(u\), \(w\) is the weight of the edge from \(u\) to \(v)\), and \(d[v]\) is the distance to node \(v)\). Input will be read from standard input, and output should be printed to standard output.

inputFormat

The input is given via standard input and consists of several lines:

1. The first line contains three integers \(n\), \(m\), and \(q\) representing the number of nodes, the number of edges, and the number of queries, respectively.
2. The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\) representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\).
3. The following \(q\) lines each contain two integers \(a\) and \(b\) representing a query to find the shortest path from node \(a\) to node \(b\).

outputFormat

For each query, output a single integer on its own line representing the shortest path distance between the two given nodes. If there is no valid path, output -1.

## sample

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

6
1

</p>