Organ Delivery Time Estimation

Ubol Narongdid founded a startup, Special D-Liver-E, for overnight organ deliveries between hospitals in the Phuket area. Given a directed road network between hospitals where each road has a fixed length (in kilometers) and an unknown speed limit (in km/h) between \(30\) and \(60\), with trucks always taking the shortest (distance‐wise) route and traveling at the road's speed limit, you are provided with two sets of data:

• The lengths of the roads connecting the hospitals.
• A set of previously executed deliveries with observed delivery times (in minutes).

Your task is to use the historical data to build an estimator for the travel time of new deliveries. For each historical delivery, the truck followed the shortest distance path; if the shortest path from hospital \(s\) to \(t\) has total length \(d\) (in km) and the observed delivery time is \(T\) (in minutes), then the effective pace for that trip is \(\frac{T}{d}\) minutes per kilometer. Combining the historical data, define an overall average pace \(P\) by

[ P = \frac{\sum_{i} T_i}{\sum_{i} d_i}, ]

and then estimate the time for any query trip from \(s\) to \(t\) by first computing the shortest distance \(d(s,t)\) (in kilometers) and then calculating

[ \text{Estimated Time} = P \times d(s,t). \quad (\text{in minutes}) ]

If no path exists between the queried hospitals, output impossible.

inputFormat

The input consists of several parts:

1. The first line contains two integers \(n\) and \(m\), representing the number of hospitals and the number of roads.
2. Then \(m\) lines follow, each containing three numbers: u v d, indicating a one-way road from hospital u to hospital v with length d kilometers.
3. The next line contains an integer \(k\), the number of historical deliveries.
4. Then \(k\) lines follow, each with three numbers: s t T where s and t are the start and end hospitals, and \(T\) is the observed delivery time (in minutes) for that trip. It is guaranteed that a path exists for each historical delivery.
5. The next line contains an integer \(q\), the number of queries.
6. Finally, \(q\) lines follow, each with two integers: s t representing a query from hospital s to hospital t.

Hospitals are numbered from 1 to \(n\>.

outputFormat

For each query, output the estimated delivery time (in minutes) computed as described. Print the result rounded to six decimal places on its own line. If there is no route from \(s\) to \(t\), output impossible.

sample

3 3
1 2 10
2 3 20
1 3 40
1
1 3 50
2
1 2
2 3

16.666667
33.333333