Ubol Narongdid is the founder of a brash new startup company
called Special DLiverE. She wants to corner the market on
overnight deliveries of organs between hospitals in the Phuket
area. For scheduling purposes it is important to have accurate
estimates for the times to perform such deliveries. Several
trips between various hospitals have already been performed, so
delivery times between those pairs of hospitals are known. The
company currently has software to estimate times for other (as
yet untraveled) trips, but so far all the estimates have been
woefully inaccurate.
You have been asked to come up with a method to improve
these estimates. You have at your disposal the following
information: 1) the length (in kilometers) of the roads
connecting each pair of cities in the Phuket area, and 2) a set
of times (in minutes) for various previously executed
deliveries.
You know that roads are oneway, and each road has a fixed
speed limit that lies between $30$ and $60$ kilometers per hour. Speed limits
are realvalued and need not be integers. You also know that
delivery trucks always take the route that minimizes distance
traveled, and on each road will always travel at a constant
speed equal to that roadâ€™s speed limit. Thus you know, for
example, that if a given trip is $50$ kilometers, the time it will take
is between $50$ and
$100$ minutes inclusive,
in the absence of any other information. Ah, but you
do have other information, namely the times of
previous deliveries. It is up to you to use it to produce the
best possible estimates.
Input
The input starts with a line containing an integer
$n$ ($1 \le n \leq 30$) indicating the
number of cities, numbered $0$ to $n1$. After that are $n$ lines each containing $n$ integers specifying the distance
in kilometers between cities: the $j^{\text {th}}$ value on the
$i^{\text {th}}$ line
indicates the distance when traveling directly from city
$i$ to city $j$. A value of $1$ indicates there is no road
directly connecting the two cities, and the distance from any
city to itself is always $0$; all other distances are positive
and at most $1\, 000$.
There are at most $100$
roads.
Following this is a line with a single integer $r$ ($1
\le r \leq 100$) indicating the number of previously
executed routes. The next $r$ lines each contain three integers
$s$, $d$, and $t$, where $s$ and $d$ are the source and destination
cities and $t$ is how long
the delivery from $s$ to
$d$ took, in minutes.
Finally there is a line containing a single integer
$q$ ($1 \le q \leq 100$) indicating the
number of future delivery queries. The next $q$ lines each contain two integers
$s$ and $d$ giving the source and destination
cities for the query.
You may assume that for each of the $r+q$ source/destination pairs in the
input there is a unique minimumdistance route.
Output
Display a single line for each query containing the source
and destination cities for that query, followed by the best low
and high bounds on the estimate for the travel time, accurate
to within an absolute or relative error of $10^{6}$.
Sample Input 1 
Sample Output 1 
3
0 50 1
55 0 40
1 40 0
1
0 2 120
3
0 1
1 2
1 0

0 1 50.0 80.0
1 2 40.0 70.0
1 0 55.0 110.0
