Shortest Path Queries

You are given an undirected weighted graph with n nodes. The graph is defined by m connections, where each connection is represented by three integers u, v and w which indicate that there is an edge between nodes u and v with weight w. You are then given q queries. Each query consists of two nodes s and t. For each query, you must compute the shortest travel time from node s to node t. If there is no path between these two nodes, output -1.

The shortest path problem can be formulated using the following equation in LaTeX form:

\( d(s,t) = \min_{\text{path } P:s \to t} \sum_{(u,v) \in P} w(u,v) \)

You are recommended to use Dijkstra's algorithm to solve this problem.

inputFormat

The input is given via stdin and has the following format:

 n m q
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm
 s1 t1
 s2 t2
 ...
 sq tq

Where:

• n is the number of nodes.
• m is the number of connections.
• q is the number of queries.
• Each of the next m lines contains three space-separated integers u, v, and w.
• Each of the next q lines contains two space-separated integers s and t representing a query.

outputFormat

For each query, output the shortest travel time from s to t on a new line via stdout. If node t is unreachable from node s, output -1.

## sample

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

6
1

</p>