#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define EPS 1e-10
#define INF 10000000000.0
 
using namespace std;
typedef long long int ll;
 
double add(double a, double b){
	if(abs(a+b)<EPS*(abs(a)+abs(b))) return 0;
	return a+b;
}
 
struct P{
	double x, y;
	P() {}
	P(double x, double y): x(x), y(y){
	}
	P operator+ (P p){
		return P(add(x, p.x), add(y, p.y));
	}
	P operator- (P p){
		return P(add(x, -p.x), add(y, -p.y));
	}
	P operator* (double d){
		return P(x*d, y*d);
	}
	double dot(P p){
		return add(x*p.x, y*p.y);
	}
	double det(P p){
		return add(x*p.y, -y*p.x);
	}
};

typedef pair<P, P> Ppair;
 
bool on_seg(P p1, P p2, P q){
	return (p1-q).det(p2-q)==0 && (p1-q).dot(p2-q)<=0;
}
 
P intersection(P p1, P p2, P q1, P q2){
	return p1+(p2-p1)*((q2-q1).det(q1-p1) / (q2-q1).det(p2-p1));
}

Ppair circ_intersection(P p1, double r1, P p2, double r2){ //2点で交わるとき
	P q=(p2-p1)*((r1*r1-r2*r2-p1.dot(p1)+p2.dot(p2))/(2.0*((p2-p1).dot(p2-p1))));
	P r=P((p2-p1).y, (p1-p2).x);
	double sq=sqrt((r.dot(q-p1))*(r.dot(q-p1))-(r.dot(r))*((q-p1).dot(q-p1)-r1*r1));
	double t1=(-(r.dot(q-p1))+sq)/(r.dot(r));
	double t2=(-(r.dot(q-p1))-sq)/(r.dot(r));
	P s1=q+r*t1, s2=q+r*t2;
	return Ppair(s1, s2);
}

int main()
{
	while(1){
		int n;
		scanf("%d", &n);
		if(n==0) return 0;
		double d[202][202];
		for(int i=0; i<2*n; i++){
			for(int j=0; j<2*n; j++){
				if(i==j){
					d[i][j]=0;
				}else{
					d[i][j]=INF;
				}
			}
		}
		P c[100];
		double r[100];
		for(int i=0; i<n; i++){
			double x, y;
			scanf("%lf %lf %lf", &x, &y, &r[i]);
			c[i]=P(x, y);
		}
		P p1[101], p2[101];
		for(int i=0; i<n-1; i++){
			Ppair p=circ_intersection(c[i], r[i], c[i+1], r[i+1]);
			p1[i]=p.first, p2[i]=p.second;
		}
		bool e0=0;
		for(int i=0; i<n-1; i++){
			if((c[0]-c[n-1]).det(p1[i]-p2[i])==0){
				e0=1;
				break;
			}
			P q=intersection(c[0], c[n-1], p1[i], p2[i]);
			if(!(on_seg(c[0], c[n-1], q) && on_seg(p1[i], p2[i], q))){
				e0=1;
				break;
			}
		}
		if(e0==0){
			printf("%.6lf\n", sqrt((c[0]-c[n-1]).dot(c[0]-c[n-1])));
			continue;
		}
		for(int i=0; i<n-1; i++){
			d[2*i+1][2*i+2]=sqrt((p1[i]-p2[i]).dot(p1[i]-p2[i]));
			d[2*i+2][2*i+1]=d[2*i+1][2*i+2];
		}
		for(int i=0; i<n-1; i++){
			bool e=0;
			for(int j=0; j<i; j++){
				if((c[0]-p1[i]).det(p1[j]-p2[j])==0){
					e=1;
					break;
				}
				P q=intersection(c[0], p1[i], p1[j], p2[j]);
				if(!(on_seg(c[0], p1[i], q) && on_seg(p1[j], p2[j], q))){
					e=1;
					break;
				}
			}
			if(e==0){
				d[0][2*i+1]=sqrt((c[0]-p1[i]).dot(c[0]-p1[i]));
				d[2*i+1][0]=d[0][2*i+1];
			}
			e=0;
			for(int j=0; j<i; j++){
				if((c[0]-p2[i]).det(p1[j]-p2[j])==0){
					e=1;
					break;
				}
				P q=intersection(c[0], p2[i], p1[j], p2[j]);
				if(!(on_seg(c[0], p2[i], q) && on_seg(p1[j], p2[j], q))){
					e=1;
					break;
				}
			}
			if(e==0){
				d[0][2*i+2]=sqrt((c[0]-p2[i]).dot(c[0]-p2[i]));
				d[2*i+2][0]=d[0][2*i+2];
			}
		}
		for(int i=0; i<n-1; i++){
			bool e=0;
			for(int j=i+1; j<n-1; j++){
				if((c[n-1]-p1[i]).det(p1[j]-p2[j])==0){
					e=1;
					break;
				}
				P q=intersection(c[n-1], p1[i], p1[j], p2[j]);
				if(!(on_seg(c[n-1], p1[i], q) && on_seg(p1[j], p2[j], q))){
					e=1;
					break;
				}
			}
			if(e==0){
				d[2*n-1][2*i+1]=sqrt((c[n-1]-p1[i]).dot(c[n-1]-p1[i]));
				d[2*i+1][2*n-1]=d[2*n-1][2*i+1];
			}
			e=0;
			for(int j=i+1; j<n-1; j++){
				if((c[n-1]-p2[i]).det(p1[j]-p2[j])==0){
					e=1;
					break;
				}
				P q=intersection(c[n-1], p2[i], p1[j], p2[j]);
				if(!(on_seg(c[n-1], p2[i], q) && on_seg(p1[j], p2[j], q))){
					e=1;
					break;
				}
			}
			if(e==0){
				d[2*n-1][2*i+2]=sqrt((c[n-1]-p2[i]).dot(c[n-1]-p2[i]));
				d[2*i+2][2*n-1]=d[2*n-1][2*i+2];
			}
		}
		for(int i=0; i<n-1; i++){
			for(int j=i+1; j<n-1; j++){
				bool e=0;
				for(int k=i+1; k<j; k++){
					if((p1[i]-p1[j]).det(p1[k]-p2[k])==0){
						e=1;
						break;
					}
					P q=intersection(p1[i], p1[j], p1[k], p2[k]);
					if(!(on_seg(p1[i], p1[j], q) && on_seg(p1[k], p2[k], q))){
						e=1;
						break;
					}
				}
				if(e==0){
					d[2*i+1][2*j+1]=sqrt((p1[i]-p1[j]).dot(p1[i]-p1[j]));
					d[2*j+1][2*i+1]=d[2*i+1][2*j+1];
				}
				e=0;
				for(int k=i+1; k<j; k++){
					if((p1[i]-p2[j]).det(p1[k]-p2[k])==0){
						e=1;
						break;
					}
					P q=intersection(p1[i], p2[j], p1[k], p2[k]);
					if(!(on_seg(p1[i], p2[j], q) && on_seg(p1[k], p2[k], q))){
						e=1;
						break;
					}
				}
				if(e==0){
					d[2*i+1][2*j+2]=sqrt((p1[i]-p2[j]).dot(p1[i]-p2[j]));
					d[2*j+2][2*i+1]=d[2*i+1][2*j+2];
				}
				e=0;
				for(int k=i+1; k<j; k++){
					if((p2[i]-p1[j]).det(p1[k]-p2[k])==0){
						e=1;
						break;
					}
					P q=intersection(p2[i], p1[j], p1[k], p2[k]);
					if(!(on_seg(p2[i], p1[j], q) && on_seg(p1[k], p2[k], q))){
						e=1;
						break;
					}
				}
				if(e==0){
					d[2*i+2][2*j+1]=sqrt((p2[i]-p1[j]).dot(p2[i]-p1[j]));
					d[2*j+1][2*i+2]=d[2*i+2][2*j+1];
				}
				e=0;
				for(int k=i+1; k<j; k++){
					if((p2[i]-p2[j]).det(p1[k]-p2[k])==0){
						e=1;
						break;
					}
					P q=intersection(p2[i], p2[j], p1[k], p2[k]);
					if(!(on_seg(p2[i], p2[j], q) && on_seg(p1[k], p2[k], q))){
						e=1;
						break;
					}
				}
				if(e==0){
					d[2*i+2][2*j+2]=sqrt((p2[i]-p2[j]).dot(p2[i]-p2[j]));
					d[2*j+2][2*i+2]=d[2*i+2][2*j+2];
				}
			}
		}

		for(int k=0; k<2*n; k++){
			for(int i=0; i<2*n; i++){
				for(int j=0; j<2*n; j++){
					if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];
				}
			}
		}
		printf("%.6lf\n", d[0][2*n-1]);
	}
	return 0;
}


Measured memory_bytes: 3540