Minimum Fuel Cost

You are given a directed weighted graph representing cities connected by routes, where each route has an associated fuel cost. Your task is to compute the minimum fuel cost required to travel from a starting city S to a destination city D for several trips. If it is not possible to reach the destination, output -1.

The problem can be formulated as follows:

Given a graph \(G=(V,E)\) with \(|V|=N\) and \(|E|=M\), and a set of trips defined by pairs \((S,D)\), determine for each trip the value $$\min_{\text{path } S\to D} \sum_{(u,v)\in \text{path}} w(u,v),$$ where \(w(u,v)\) is the fuel cost associated with the route from \(u\) to \(v\). If no such path exists, output -1.

inputFormat

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

N M T
u1 v1 w1
u2 v2 w2
... (M lines total)
S1 D1
S2 D2
... (T lines total)

Where:

• N: Number of cities (nodes).
• M: Number of routes (directed edges).
• T: Number of trips.
• Each of the next M lines contains three integers u, v, and w, representing a route from city u to city v with fuel cost w.
• Each of the next T lines contains two integers S and D, representing the source and destination cities for a trip.
</p>

outputFormat

For each trip, output a single line containing the minimum fuel cost needed to travel from S to D. If there is no path from S to D, output -1.

## sample

4 4 2
0 1 10
0 2 15
1 3 20
2 3 30
0 3
1 2

30
-1

</p>