Taco Delivery

You are given a directed weighted graph representing roads connecting warehouses. Each node denotes a warehouse and each edge represents a road with a travel time. Your task is to determine the fastest delivery route from a source warehouse \( s \) to a destination warehouse \( d \) for multiple queries using Dijkstra's algorithm. If there is no path between the given warehouses, return \( -1 \).

The graph may include self-loops, which should not affect the shortest path calculations. Solve each query efficiently.

inputFormat

The first line contains three integers ( n ), ( m ), and ( k ), where ( n ) is the number of warehouses, ( m ) is the number of roads, and ( k ) is the number of queries. The next ( m ) lines each contain three integers ( u ), ( v ), and ( t ), representing a road from warehouse ( u ) to warehouse ( v ) with travel time ( t ). The following ( k ) lines each contain two integers ( s ) and ( d ), representing a query from warehouse ( s ) to warehouse ( d ).

outputFormat

For each query, print a single line containing the minimum travel time from ( s ) to ( d ). If no such route exists, print ( -1 ).## sample

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

10
5
3
7
-1