Taco Traffic Network

This problem simulates network traffic requests over a bidirectional network. The network contains n nodes and m links, where each link connects two nodes and has a specified bandwidth. You will be given r data transfer requests. For each request from a source node s to a destination node d requesting an amount a of data, determine the maximum data that can be transferred. This is computed as the minimum of the maximum flow (calculated using the Edmonds-Karp algorithm) available from s to d and the desired amount a.

The input terminates with a dataset that starts with 0. Your program should process all datasets and output the result for each transfer request.

Note: The maximum flow between two nodes can be expressed in terms of the capacity constraints along a path. In LaTeX, if you consider a path with capacities \( c_1, c_2, \dots, c_k \), the maximum flow is limited by \( \min\{ c_1, c_2, \dots, c_k \} \).

inputFormat

The input consists of multiple datasets. Each dataset is defined as follows:

• The first line contains three integers: n (number of nodes), m (number of bidirectional links), and r (number of transfer requests).
• The next m lines each contain three integers u, v and b indicating a bidirectional link between nodes u and v with bandwidth b.
• The following r lines each contain three integers s, d and a representing a transfer request from source s to destination d with a requested data amount a.

The input terminates with a line starting with a single 0.

outputFormat

For each transfer request in all datasets, output a single integer on a new line representing the maximum data that can be transferred (i.e. \( \min(\text{max flow}, a) \)).

## sample

4 5 3
0 1 10
0 2 5
1 2 15
1 3 10
2 3 5
0 3 10
1 2 7
0 1 12
0

10
7
12

</p>