Minimum Toll Cost

You are given a network of intersections connected by bidirectional roads where each road has an associated toll cost. Your task is to answer multiple queries asking for the minimum toll cost needed to travel from one intersection to another.

If there is no possible route between the queried intersections, output -1.

This problem can be efficiently solved using Dijkstra's algorithm for single-source shortest paths. In the context of this problem, intersections are labeled from 1 to N.

The toll cost for a route is the sum of the tolls of the roads taken.

Note: All roads are bidirectional.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains three space-separated integers N, M, and Q, representing the number of intersections, the number of roads, and the number of queries respectively.

The next M lines each contain three integers u, v, w where u and v are the intersections connected by a road and w is the toll cost of that road.

The following Q lines each contain two integers S and T representing a query asking for the minimum toll cost to travel from intersection S to intersection T.

outputFormat

For each query, output a single line containing the minimum toll cost from intersection S to intersection T. If it is not possible to travel from S to T, output -1.## sample

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

5
4
6