Network Delay Time

You are given an undirected weighted network of computers connected by cables. Each cable connects two computers and has an associated delay time. Your task is to compute the minimum delay required to send a data packet from a source computer to a destination computer for several query configurations.

The network can be modeled as a graph where the nodes represent computers and the edges (with weights) represent the delay time of the cables. For a given query with source X and destination Y, you need to determine the shortest path delay from X to Y. If there is no valid path from X to Y, output -1.

The delay for a path \(P\) is defined as:

\( d(X,Y) = \min_{P:\, X \to Y} \sum_{(i,j) \in P} T_{ij} \)

inputFormat

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

• The first line contains three integers: n (number of computers), m (number of cables), and c (number of configurations/queries), separated by spaces.
• The next m lines each contain three integers A, B, and T, representing a cable connecting computer A and B with delay time T.
• The next c lines each contain two integers X and Y, representing a query asking for the minimum delay from computer X to computer Y.

outputFormat

For each of the c queries, output the minimum delay time on a new line. If there is no path from the source to the destination, output -1.

## sample

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

6
7

</p>