Shortest Travel Time

You are given an undirected weighted graph representing intersections (nodes) and roads (edges). Each road connects two intersections and has a positive travel time. For a given set of queries, you are to determine the minimum travel time between two intersections. If there is no route between the given intersections, output -1.

Mathematically, for two intersections (u) and (v), you need to compute:

[ d(u,v)=\min_{\text{path }P: u \to v}\sum_{e \in P} w(e) ]

where (w(e)) is the weight (travel time) of edge (e). This problem is conventionally solved using Dijkstra’s algorithm.

inputFormat

The first line contains three integers (n), (m) and (q) representing the number of intersections, roads, and queries respectively. The following (m) lines each contain three integers (u), (v), and (w), meaning there is a road between intersections (u) and (v) with travel time (w). The next (q) lines each contain two integers (a) and (b), representing a query asking for the shortest travel time from intersection (a) to intersection (b).

outputFormat

For each query, output the shortest travel time on a separate line. If no path exists between the two intersections, output -1.## sample

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

15
12