광섬유 네트워크

어느 개발도상국이 통신 기반 시설을 개선하려고 한다. 현재 이 나라의 각 도시는 자체 지역 컴퓨터 네트워크를 가지고 있지만, 도시 사이를 잇는 빠른 통신망은 없다. 이 나라의 통신부는 모든 도시를 연결하는 빠른 광섬유 네트워크를 구축하기로 했다.

도시들을 연결하기 위해, 선택된 몇 쌍의 도시 사이에 광섬유 회선을 설치한다. 비용을 줄이기 위해, 임의의 두 도시 사이에는 광섬유 경로가 정확히 하나만 존재하도록 회선을 고른다. 즉, $N$개의 도시와 $N-1$개의 회선은 하나의 트리를 이룬다.

각 도시에는 광 라우터를 하나 설치하며, 그 도시를 끝점으로 하는 모든 광섬유 회선은 이 라우터에 연결된다. 각 도시에는 라우터를 설치할 수 있는 후보 위치가 여러 곳 있다. 프로젝트에 필요한 광섬유의 총 길이가 최소가 되도록, 각 도시마다 라우터를 설치할 위치를 하나씩 정하는 것이 목표이다.

회선 하나의 길이는 그 회선이 연결하는 두 도시에서 각각 선택한 위치 사이의 유클리드 거리이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 도시의 수 $N$ ($1 \le N \le 1000$)이 주어진다.

이어서 각 도시에 대한 정보가 주어진다. 각 도시의 첫 줄에는 도시의 (서로 다른) 이름(대문자로만 이루어지며 길이는 최대 15)과 라우터를 설치할 수 있는 후보 위치의 수 $C_i$ ($1 \le C_i \le 50$)가 주어진다. 다음 $C_i$개의 줄에는 각 후보 위치의 좌표를 나타내는 두 정수 $X$와 $Y$ ($-10000 \le X, Y \le 10000$)가 주어진다.

모든 도시의 정보가 끝나면 $N-1$개의 줄이 이어지며, 각 줄에는 광섬유 회선으로 연결할 두 도시의 이름이 주어진다.

입력의 끝은 $N = 0$으로 표시된다.

각 테스트 케이스마다 모든 도시를 연결하는 데 필요한 광섬유의 최소 총 길이를 한 줄에 출력한다. 답은 소수점 아래 한 자리로 반올림하여 출력한다.