Minimum Bus Travel Time

You are given a bus network consisting of N stops and M directed bus routes. Each route is represented by a triple \( (U, V, W) \), which means there is a bus from stop \( U \) to stop \( V \) with a travel time of \( W \).

Your task is to process \( Q \) queries. Each query gives you two integers \( S \) and \( D \) and asks for the minimum travel time required to reach stop \( D \) starting from stop \( S \). If stop \( D \) cannot be reached from \( S \), output -1.

You may use Dijkstra's algorithm to efficiently compute the shortest path in this network. Note that since all travel times are non-negative, Dijkstra's algorithm is applicable.

inputFormat

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

• The first line contains three integers \( N \), \( M \), and \( Q \): the number of bus stops, the number of bus routes, and the number of queries.
• The next \( M \) lines each contain three integers \( U \), \( V \), and \( W \), describing a bus route from stop \( U \) to stop \( V \) with travel time \( W \).
• The following \( Q \) lines each contain two integers \( S \) and \( D \), representing a query asking for the minimum travel time from stop \( S \) to stop \( D \).

outputFormat

For each query, output the minimum travel time required to travel from ( S ) to ( D ) on a separate line. If there is no valid route from ( S ) to ( D ), output -1.## sample

5 6 3
1 2 10
2 3 10
3 4 10
1 3 30
4 5 10
1 5 50
1 5
1 4
2 1

40
30
-1