Warp Drive

Warp drive technology is changing air travel. An aircraft that reaches the airspace above a warp field built on the ground is transferred to its destination in an instant.

With the current technology a warp field is expensive, and the budget covers only two of them. The cost does not depend on the location, so you may build them anywhere on the ground, including on an airport.

You are given the locations of the airports and a list of one way flights between them. Find where to build the two warp fields so that the average cost is as small as possible, and report that average cost. The average cost is the root mean square of the travel times of all the flights.

$\sqrt{\frac{1}{m}\sum_{j=1}^{m} t_j^{2}}$

Here $m$ is the number of flights and $t_j$ is the shortest possible travel time of the $j$-th flight. The value of $t_j$ depends on where the warp fields are.

To keep the model simple, the ground is a flat plane, and airports, aircraft and warp fields are points on that plane. Different flights use different aircraft, so their cruising speeds may differ. The time needed to climb, accelerate, decelerate and descend is 0. Once an aircraft reaches the airspace above a warp field, the time it needs after that to reach its destination is 0. Airport coordinates are integers, but warp field coordinates do not have to be.

So if the warp fields are placed at $P$ and $Q$, a flight that departs from airport $A$, arrives at airport $B$ and cruises at speed $v$ takes

$t = \frac{\min(|AB|, |AP|, |AQ|)}{v}$

The input has at most 35 datasets, each in the following format.

n m
x1 y1
...
xn yn
a1 b1 v1
...
am bm vm

$n$ is the number of airports and $m$ is the number of flights ($2 \le n \le 20$, $2 \le m \le 40$). In the next $n$ lines, $x_i$ and $y_i$ are the coordinates of airport $i$, integers with absolute value at most 1000. In the next $m$ lines, $a_j$ and $b_j$ are the departure and the arrival airport number of the $j$-th flight, integers between 1 and $n$. $v_j$ is the cruising speed of the $j$-th flight, that is, the distance its aircraft moves in one time unit. $v_j$ is given with two digits after the decimal point and satisfies $1 \le v_j \le 10$.

The following hold.

• Two different airports have different coordinates.
• The departure airport and the arrival airport of every flight are different.
• Two different flights differ in the departure airport, in the arrival airport, or in both.

The end of the input is a line containing two zeros.

For each dataset, print the average cost obtained by placing the two warp fields optimally, one value per line. Round the value to exactly 6 digits after the decimal point.