원들 감싸기

여러 개의 원이 주어진다. 어떤 원은 다른 원과 만나지 않을 수도 있고, 일부 원과 겹칠 수도 있으며, 다른 원을 완전히 감싸거나 감싸질 수도 있다.

그림 1. 주어진 원들

그림 2. 밧줄의 배치

이 원들을 모두 밧줄로 감싸려고 한다. 물론 밧줄의 길이는 최소가 되어야 한다. 예를 들어 그림 1의 원들이 주어지면 밧줄은 그림 2처럼 놓인다.

밧줄의 배치를 구하고 밧줄의 최소 길이를 계산하는 프로그램을 작성하라. 밧줄의 두께는 무시한다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

n
x1 y1 r1
x2 y2 r2
...
xn yn rn

데이터 세트의 첫 줄에는 원의 개수인 정수 n이 주어진다. n은 양수이고 100을 넘지 않는다.

다음 n개의 줄은 원의 정보를 나타낸다. 한 줄에 있는 세 값은 차례대로 원 중심의 x좌표, y좌표, 반지름(이 문제의 나머지 부분에서는 r이라 부른다)이다. 각 값은 소수점 아래 3자리까지 있는 소수로 주어지며, 값은 공백 문자로 구분된다.

x, y, r은 각각 0.01보다 작지 않고 100.0보다 크지 않다. 두 원이 같은 경우는 없다. 더 정확히 말하면, 두 원의 x, y, r 중 적어도 하나는 차이가 0.01보다 크다.

입력의 끝은 0이 들어 있는 줄로 표시된다.

각 데이터 세트마다 밧줄의 최소 길이를 한 줄에 하나씩 출력한다. 출력하는 값은 소수점 아래 5자리까지 있어야 한다. 오차는 0.00001보다 클 수 없다.