워프 드라이브

워프 드라이브 기술이 항공 여행을 바꾸고 있다. 지표면에 세운 워프 필드 위에 도달한 항공기는 원하는 목적지로 즉시 이동한다.

지금 기술로는 워프 필드를 세우는 비용이 커서 예산으로 두 개만 지을 수 있다. 대신 비용은 위치와 무관하므로 지표면 어디에나 세울 수 있고, 공항 위에 세워도 된다.

공항 위치와 공항 사이를 오가는 일방통행 항공편 목록이 주어진다. 평균 비용이 가장 작아지도록 워프 필드 두 개의 위치를 정하고, 그때의 평균 비용을 구하라. 평균 비용은 모든 항공편 이동 시간의 제곱평균제곱근이다.

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

$m$은 항공편 수이고 $t_j$는 $j$번째 항공편이 걸리는 최단 시간이다. $t_j$ 값은 워프 필드의 위치에 따라 달라진다.

문제를 단순하게 만들기 위해 지표면은 평면으로 보고, 공항과 항공기와 워프 필드는 평면 위의 점으로 본다. 항공편마다 항공기가 다르므로 순항 속력도 다를 수 있다. 상승, 가속, 감속, 하강에 걸리는 시간은 0이다. 항공기가 워프 필드 위에 도달하면 그 뒤 목적지까지 걸리는 시간은 0이다. 공항 좌표는 정수이지만 워프 필드 좌표는 정수가 아니어도 된다.

따라서 워프 필드를 $P$와 $Q$에 놓으면, 출발 공항이 $A$이고 도착 공항이 $B$이며 순항 속력이 $v$인 항공편의 최단 시간은 다음과 같다.

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

입력은 데이터 세트 35개 이하로 이루어지고, 각 데이터 세트의 형식은 다음과 같다.

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

$n$은 공항 수, $m$은 항공편 수이다 ($2 \le n \le 20$, $2 \le m \le 40$). 이어지는 $n$개 줄의 $x_i$와 $y_i$는 $i$번 공항의 좌표이고, 절댓값이 1000 이하인 정수이다. 그다음 $m$개 줄의 $a_j$와 $b_j$는 $j$번째 항공편의 출발 공항 번호와 도착 공항 번호이고, 1 이상 $n$ 이하의 정수이다. $v_j$는 $j$번째 항공편의 순항 속력, 즉 그 항공기가 시간 1 동안 이동하는 거리이다. $v_j$는 소수점 아래 두 자리까지 주어지며 1 이상 10 이하이다.

다음을 만족한다.

• 서로 다른 두 공항의 좌표는 다르다.
• 모든 항공편의 출발 공항과 도착 공항은 서로 다르다.
• 서로 다른 두 항공편은 출발 공항과 도착 공항 가운데 적어도 하나가 다르다.

입력의 끝은 0이 두 개 적힌 줄로 나타낸다.

각 데이터 세트마다 워프 필드 두 개를 가장 좋은 위치에 놓았을 때의 평균 비용을 한 줄에 하나씩 출력한다. 값은 소수점 아래 여섯째 자리까지 반올림해서 출력한다.