Shortest Paths in Directed Road Network

This problem requires you to compute the shortest travel time between pairs of warehouses in a directed road network. The network consists of n warehouses and m one-way roads, each associated with a travel time. You will be given q queries, each asking for the minimum time required to travel from a source warehouse to a destination warehouse. If there is no possible route, output -1.

For each query, you need to calculate the shortest path using a suitable algorithm such as Dijkstra's algorithm. Note that the time complexity of an efficient implementation is typically \(O((n + m) \log n)\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) which represent the number of warehouses, the number of roads, and the number of queries, respectively.

The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), indicating there is a directed road from warehouse \(u\) to warehouse \(v\) with travel time \(w\).

The following \(q\) lines each contain two integers \(s\) and \(t\), representing a query asking for the shortest travel time from warehouse \(s\) to warehouse \(t\).

outputFormat

For each query, output a single line containing the minimum travel time from the source to the destination warehouse. If no path exists, output -1.

## sample

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

30
20

</p>