사슬에 갇힌 최단 경로

평면 위에 여러 개의 원으로 이루어진 사슬이 있다. 사슬의 첫 번째 원은 두 번째 원하고만 만나고, 마지막 원은 바로 앞 원하고만 만나며, 그 사이의 각 원은 자신의 양옆 두 원하고만 만난다.

다음 두 조건을 모두 만족하는 최단 경로를 구하라.

• 경로는 첫 번째 원의 중심과 마지막 원의 중심을 잇는다.
• 경로는 사슬 안에 갇혀 있다. 즉 경로 위의 모든 점은 적어도 하나의 원 내부 또는 그 경계 위에 있다.

아래 그림은 이러한 사슬과 그에 대응하는 최단 경로의 예이다.

사슬과 그에 대응하는 최단 경로의 예.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 하나의 사슬을 다음 형식으로 나타낸다.

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

데이터셋의 첫 줄에는 원의 개수를 나타내는 정수 $n$ ($3 \le n \le 100$)이 주어진다. 이어지는 $n$개의 줄에는 각각 공백 하나로 구분된 정수 세 개가 주어지며, $(x_i, y_i)$는 $i$번째 원 $C_i$의 중심, $r_i$은 그 반지름이다. $0 \le x_i \le 1000$, $0 \le y_i \le 1000$, $1 \le r_i \le 25$임이 보장된다.

$C_i$와 $C_{i+1}$ ($1 \le i \le n-1$)은 서로 다른 두 점에서 만난다. $j \ge i+2$인 경우 $C_i$와 $C_j$는 서로 떨어져 있으며 어느 쪽도 다른 쪽을 포함하지 않는다. 또한 어떤 원도 다른 원의 중심을 포함하지 않는다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

아래 그림은 여러 사슬 예에 대한 최단 경로를 보여준다.

여러 사슬 예와 그에 대응하는 최단 경로.

각 데이터셋에 대해, 첫 번째 원의 중심과 마지막 원의 중심을 잇는 사슬에 갇힌 최단 경로의 길이를 한 줄에 하나씩 출력한다. 값은 소수점 아래 정확히 여섯 자리까지 출력한다(예: 16.000000). 그 외의 문자는 출력하지 않는다.