#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)

const double EPS=1e-7;
const double INF=1e77;

template<class T>
struct point{
	T x,y;
	point operator+(const point &a)const{ return (point){x+a.x,y+a.y}; }
	point operator-(const point &a)const{ return (point){x-a.x,y-a.y}; }
};

template<class T>
point<T> operator*(T c,const point<T> &a){ return (point<T>){c*a.x,c*a.y}; }

template<class T>
bool operator<(const point<T> &a,const point<T> &b){ return a.x+EPS<b.x || abs(a.x-b.x)<EPS && a.y+EPS<b.y; }

template<class T>
struct line{
	point<T> a,b;
};

template<class T>
struct segment{
	point<T> a,b;
	operator line<T>()const{ return (line<T>){a,b}; }
};

template<class T>
struct circle{
	point<T> c;
	T r;
};

template<class T>
double abs(const point<T> &a){ return sqrt(a.x*a.x+a.y*a.y); }

template<class T>
T abs2(const point<T> &a){ return a.x*a.x+a.y*a.y; }

int get_intersect(const circle<double> &C1,const circle<double> &C2,vector< point<double> > &res){
	double r1=C1.r,r2=C2.r;
	point<double> p1=C1.c,p2=C2.c;

	double d=abs(p1-p2);
	if(d<EPS && abs(r1-r2)<EPS){
		return -1;
	}
	else if(r1+r2<d-EPS || d+EPS<abs(r1-r2)){
		return 0;
	}
	else{
		double a=(r1*r1-r2*r2+d*d)/(2*d);
		double h=sqrt(max(r1*r1-a*a,0.0));
		point<double> tmp1=p1+a/d*(p2-p1);
		point<double> tmp2=h/d*(p2-p1);
		if(abs(tmp2)<EPS){
			res.push_back(tmp1);
			return 1;
		}
		else{
			res.push_back((point<double>){tmp1.x-tmp2.y,tmp1.y+tmp2.x});
			res.push_back((point<double>){tmp1.x+tmp2.y,tmp1.y-tmp2.x});
			return 2;
		}
	}
}

template<class T>
T dot(const point<T> &a,const point<T> &b){
	return a.x*b.x+a.y*b.y;
}

template<class T>
point<double> proj(const point<T> &p,const line<T> &L){
	return L.a+dot(p-L.a,L.b-L.a)/abs2(L.b-L.a)*(L.b-L.a);
}

template<class T>
double dist(const point<T> &a,const point<T> &b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool cover(const segment<double> &S,const point<double> &p){
	return dist(S.a,p)+dist(p,S.b)<dist(S.a,S.b)+EPS;
}

int get_intersect(const circle<double> &C,const segment<double> &S,vector< point<double> > &res){
	point<double> h=proj(C.c,line<double>(S));
	double d=dist(C.c,h);
	if(d>C.r+EPS) return 0;
	if(d>C.r-EPS){
		int cnt=0;
		if(cover(S,h)) res.push_back(h), cnt++;
		return cnt;
	}
	else{
		point<double> v=S.b-S.a;
		v=(sqrt(C.r*C.r-d*d)/abs(v))*v;
		int cnt=0;
		if(cover(S,h+v))  res.push_back(h+v), cnt++;
		if(cover(S,h-v))  res.push_back(h-v), cnt++;
		return cnt;
	}
}

bool cover(const circle<double> &C,const point<double> &p){
	return dist(C.c,p)<C.r+EPS;
}

int main(){
	for(int n;scanf("%d",&n),n;){
		circle<double> C[100];
		rep(i,n) scanf("%lf%lf%lf",&C[i].c.x,&C[i].c.y,&C[i].r);
		vector< point<double> > P;
		P.push_back(C[0].c);
		P.push_back(C[n-1].c);
		rep(i,n-1) get_intersect(C[i],C[i+1],P);

		int m=P.size();
		static double d[300][300]={};
		rep(i,m) rep(j,m) if(i!=j) {
			vector< point<double> > Q;
			Q.push_back(P[i]);
			Q.push_back(P[j]);
			rep(k,n) get_intersect(C[k],(segment<double>){P[i],P[j]},Q);
			sort(Q.begin(),Q.end());

			bool ok=true;
			rep(k,(int)Q.size()-1){
				point<double> c=0.5*(Q[k]+Q[k+1]);
				bool ok2=false;
				rep(l,n) if(cover(C[l],c)) { ok2=true; break; }
				if(!ok2){ ok=false; break; }
			}
			if(ok){
				d[i][j]=abs(P[i]-P[j]);
			}
			else{
				d[i][j]=INF;
			}
		}

		rep(k,m) rep(i,m) rep(j,m) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

		printf("%.9f\n",d[0][1]);
	}

	return 0;
}

Measured memory_bytes: 1356