#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <complex>

using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl
//#define DEBUG(x) 

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EPS 1e-9
#define INT(a) int((a)+1e-9)
int DX[4]={1,0,-1,0};
int DY[4]={0,1,0,-1};

typedef pair<int,int> Pii;
typedef complex<double> Point;

double dotProd(Point ap, Point bp){
	return real(conj(ap)*bp);
}
double croProd(Point ap, Point bp){
	return imag(conj(ap)*bp);
}

Point rotated(Point p, double th){
	return Point(cos(th), sin(th)) * p;
};

struct Line{
	Point ap;
	Point bp;
	Point dp;
	Line(){}
	Line(Point ap_, Point bp_){ ap=ap_; bp=bp_; dp=bp-ap;}
};

struct Segline{
	Point ap;
	Point bp;
	Point dp;
	Segline(){}
	Segline(Point ap_, Point bp_){ ap=ap_; bp=bp_; dp=bp-ap;}
	double length(){ return abs(dp);}
};

struct Circle{
	Point cp;
	double r;
	Circle(){}
	Circle(Point cp_, double r_){ cp=cp_; r=r_;}
};

Segline getSeglineOfCrossingPoints_Circle_Circle(Circle m, Circle n){
	double d = abs(n.cp-m.cp);
	double x = (d*d+m.r*m.r-n.r*n.r)/(2*d);
	double y = sqrt(m.r*m.r-x*x);
	double th= arg(n.cp-m.cp);
	Point ap = rotated(Point(x,y),th) + m.cp;
	Point bp = rotated(Point(x,-y), th) + m.cp;
	return Segline(ap,bp);
}

bool isCross_Line_Segline(Line m, Segline n){
	double det=croProd(m.dp,n.dp);
	if(abs(det)<EPS) return false;
	double s=croProd(n.dp, m.ap-n.ap)/det;
	double t=croProd(m.dp, m.ap-n.ap)/det;
	//DEBUG(s);DEBUG(t);
	if(0-EPS<=t && t<=1+EPS) return true;
	else return false;
}


#define SUPcl 102
#define INF 1e+9

int cl;
Circle cs[SUPcl];
Segline segs[SUPcl];
Circle startc;
Circle endc;
double startc_endc_w;
double startc_c_w[SUPcl][2];
double c_endc_w[SUPcl][2];
double c_c_w[SUPcl][2][SUPcl][2];
double c_d[SUPcl][2];
double re;

void calc_segs(){
	FOR(ci,0,cl-1){
		Segline l = getSeglineOfCrossingPoints_Circle_Circle(cs[ci],cs[ci+1]);
		segs[ci]=l;
		//DEBUG(ci); DEBUG(l.ap); DEBUG(l.bp);
	}
}

double calc_startc_endc_w(){
	Line m = Line(startc.cp, endc.cp);
	startc_endc_w=abs(m.dp);
	FOR(ci,0,cl-1){
		Segline n=segs[ci];
		if(!isCross_Line_Segline(m,n)){startc_endc_w=INF; break;}
	}
	//DEBUG(startc_endc_w);
}
double calc_startc_c_w(){
	FOR(cj,0,cl-1) FOR(j,0,2){
		Line m = Line(startc.cp, j ? segs[cj].bp : segs[cj].ap);
		startc_c_w[cj][j]=abs(m.dp);
		FOR(ck,0,cj){
			Segline n=segs[ck];
			if(!isCross_Line_Segline(m,n)){startc_c_w[cj][j]=INF; break;}
		}
		//DEBUG(cj);DEBUG(j);DEBUG(startc_c_w[cj][j]);
	}
}
double calc_c_endc_w(){
	FOR(ci,0,cl-1) FOR(i,0,2){
		Line m = Line(i ? segs[ci].bp : segs[ci].ap, endc.cp);
		c_endc_w[ci][i]=abs(m.dp);
		FOR(ck,ci+1,cl-1){
			Segline n=segs[ck];
			if(!isCross_Line_Segline(m,n)){c_endc_w[ci][i]=INF; break;}
		}
		//DEBUG(ci);DEBUG(i);DEBUG(c_endc_w[ci][i]);
	}
}
double calc_c_c_w(){
	FOR(ci,0,cl-1) FOR(i,0,2) FOR(cj,ci+1,cl-1) FOR(j,0,2){
		Line m = Line(i ? segs[ci].bp : segs[ci].ap, j ? segs[cj].bp : segs[cj].ap);
		c_c_w[ci][i][cj][j]=abs(m.dp);
		FOR(ck,ci+1,cj){
			Segline n=segs[ck];
			if(!isCross_Line_Segline(m,n)){c_c_w[ci][i][cj][j]=INF; break;}
		}
		//DEBUG(ci);DEBUG(i);DEBUG(cj);DEBUG(j);DEBUG(c_c_w[ci][i][cj][j]);
	}
}

double calc_c_d(){
	FOR(cj,0,cl-1) FOR(j,0,2){
		c_d[cj][j]= startc_c_w[cj][j];
	}
	FOR(ci,0,cl-1) FOR(i,0,2) FOR(cj,ci+1,cl-1) FOR(j,0,2){
		c_d[cj][j]= min( c_d[cj][j], c_d[ci][i] + c_c_w[ci][i][cj][j] );
	}
}

double calc_re(){
	re=startc_endc_w;
	FOR(ci,0,cl-1) FOR(i,0,2){
		re = min(re, c_d[ci][i] + c_endc_w[ci][i]);
	}
}




int main(){
	while(true){
		cin>>cl;		if(!cl)break;
		FOR(ci,0,cl){
			int x,y,r;
			cin>>x>>y>>r;
			cs[ci]=Circle(Point(x,y),r);
		}
		calc_segs();
		startc=cs[0]; endc=cs[cl-1];
		calc_startc_endc_w();
		calc_startc_c_w();
		calc_c_endc_w();
		calc_c_c_w();
		calc_c_d();
		calc_re();
		cout<<fixed<<setprecision(7)<<re<<endl;

	}	
}

Measured memory_bytes: 1648