#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

const double PI=acos(-1);

int Signum(double x){
	return abs(x)<EPS?0:x<0?-1:1;
}

struct Point{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
};
bool operator==(Point a,Point b){
	return abs(a.x-b.x)<EPS && abs(a.y-b.y)<EPS;
}
bool operator!=(Point a,Point b){
	return !(a==b);
}
Point operator+(Point a,Point b){
	return Point(a.x+b.x,a.y+b.y);
}
Point operator-(Point a,Point b){
	return Point(a.x-b.x,a.y-b.y);
}
Point operator*(double c,Point p){
	return Point(c*p.x,c*p.y);
}
Point operator/(Point p,double c){
	return Point(p.x/c,p.y/c);
}
double Abs(Point p){
	return sqrt(p.x*p.x+p.y*p.y);
}
double Abs2(Point p){
	return p.x*p.x+p.y*p.y;
}
double Dot(Point a,Point b){
	return a.x*b.x+a.y*b.y;
}
double Cross(Point a,Point b){
	return a.x*b.y-a.y*b.x;
}
Point Rot(Point p,double t){
	return Point(cos(t)*p.x-sin(t)*p.y,sin(t)*p.x+cos(t)*p.y);
}


int CCW(Point a,Point b,Point c){
	Point d1=b-a,d2=c-a;
	if(int sign=Signum(Cross(d1,d2)))
		return sign;	// 1:ccw,-1:cw
	if(Dot(d1,d2)<-EPS)
		return -2;		// c-a-b
	if(Abs2(d1)<Abs2(d2)-EPS)
		return 2;		// a-b-c
	return 0;			// a-c-b
}

struct Circle{
	Point center;
	double radius;
	Circle(){}
	Circle(Point c,double r):center(c),radius(r){}
	Circle(double x,double y,double r):center(x,y),radius(r){}
};

ostream& operator<<(ostream& os,const Point& p){
	return os<<'('<<p.x<<','<<p.y<<')';
}
ostream& operator<<(ostream& os,const Circle& c){
	return os<<'('<<c.center.x<<','<<c.center.y<<','<<c.radius<<')';
}

pair<Point,Point> InterCC(Circle c1,Circle c2){
	Point p1=c1.center,p2=c2.center;
	double r1=c1.radius,r2=c2.radius;
	double d=Abs(p1-p2);
	double a=(d*d+r1*r1-r2*r2)/(2*d);
	double s=sqrt(r1*r1-a*a);
	return mp(p1+a/d*(p2-p1)+s*Rot((p2-p1)/d,PI/2),
			  p1+a/d*(p2-p1)-s*Rot((p2-p1)/d,PI/2));
}

int main()
{
	for(int n;cin>>n,n;){
		vector<Circle> cs(n);
		rep(i,n) cin>>cs[i].center.x>>cs[i].center.y>>cs[i].radius;
		
		vector<pair<Point,Point> > ps(n-1);
		rep(i,n-1)
			ps[i]=InterCC(cs[i],cs[i+1]);
		
		vvd dp(2*n,vd(2*n,INFTY));
		rep(i,n-1) repi(j,i,n-1){
			if(i==j){
				dp[i*2+0][i*2+0]=dp[i*2+1][i*2+1]=0;
				dp[i*2+0][i*2+1]=dp[i*2+1][i*2+0]=Abs(ps[i].first-ps[i].second);
				continue;
			}
			
			Point pi1=ps[i].first,pi2=ps[i].second;
			Point pj1=ps[j].first,pj2=ps[j].second;
			bool flg11=true,flg12=true,flg21=true,flg22=true;
			repi(k,i+1,j){
				Point pk1=ps[k].first,pk2=ps[k].second;
				flg11&=CCW(pi1,pk1,pj1)*CCW(pi1,pk2,pj1)<=0;
				flg12&=CCW(pi1,pk1,pj2)*CCW(pi1,pk2,pj2)<=0;
				flg21&=CCW(pi2,pk1,pj1)*CCW(pi2,pk2,pj1)<=0;
				flg22&=CCW(pi2,pk1,pj2)*CCW(pi2,pk2,pj2)<=0;
			}
			if(flg11) dp[i*2+0][j*2+0]=dp[j*2+0][i*2+0]=Abs(pi1-pj1);
			if(flg12) dp[i*2+0][j*2+1]=dp[j*2+1][i*2+0]=Abs(pi1-pj2);
			if(flg21) dp[i*2+1][j*2+0]=dp[j*2+0][i*2+1]=Abs(pi2-pj1);
			if(flg22) dp[i*2+1][j*2+1]=dp[j*2+1][i*2+1]=Abs(pi2-pj2);
		}
		int src=2*(n-1),dst=src+1;
		dp[src][src]=dp[dst][dst]=0;
		rep(j,n-1){
			Point psrc=cs[0].center,pj1=ps[j].first,pj2=ps[j].second;
			bool flgs1=true,flgs2=true;
			rep(k,j){
				Point pk1=ps[k].first,pk2=ps[k].second;
				flgs1&=CCW(psrc,pk1,pj1)*CCW(psrc,pk2,pj1)<=0;
				flgs2&=CCW(psrc,pk1,pj2)*CCW(psrc,pk2,pj2)<=0;
			}
			if(flgs1) dp[src][j*2+0]=dp[j*2+0][src]=Abs(psrc-pj1);
			if(flgs2) dp[src][j*2+1]=dp[j*2+1][src]=Abs(psrc-pj2);
		}
		rep(i,n-1){
			Point pdst=cs[n-1].center,pi1=ps[i].first,pi2=ps[i].second;
			bool flgd1=true,flgd2=true;
			peri(k,i+1,n-1){
				Point pk1=ps[k].first,pk2=ps[k].second;
				flgd1&=CCW(pdst,pk1,pi1)*CCW(pdst,pk2,pi1)<=0;
				flgd2&=CCW(pdst,pk1,pi2)*CCW(pdst,pk2,pi2)<=0;
			}
			if(flgd1) dp[dst][i*2+0]=dp[i*2+0][dst]=Abs(pdst-pi1);
			if(flgd2) dp[dst][i*2+1]=dp[i*2+1][dst]=Abs(pdst-pi2);
		}
		{
			Point psrc=cs[0].center,pdst=cs[n-1].center;
			bool flgsd=true;
			rep(k,n-1){
				Point pk1=ps[k].first,pk2=ps[k].second;
				flgsd&=CCW(psrc,pk1,pdst)*CCW(psrc,pk2,pdst)<=0;
			}
			if(flgsd) dp[src][dst]=dp[dst][src]=Abs(psrc-pdst);
		}
		
		rep(k,2*n) rep(i,2*n) rep(j,2*n)
			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
		printf("%f\n",dp[src][dst]);
	}
	
	return 0;
}

Measured memory_bytes: 1532