#include <bits/stdc++.h>
using namespace std;

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) gnr(i,0,b)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
#define tmp template<class t>

tmp void chmax(t&a,t b){if(a<b)a=b;}
tmp void chmin(t&a,t b){if(a>b)a=b;}

tmp using vc=vector<t>;
tmp using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

tmp ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

tmp void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll read(){ll i;cin>>i;return i;}

using ld=long double;
using cm=complex<ld>;
#define x real()
#define y imag()
const ld eps=1e-7;
int sgn(ld a){return a<-eps?-1:(a>eps?1:0);}
auto cmcmp=[](const cm&a,const cm&b){
	if(sgn(a.x-b.x))return a.x<b.x;
	else return sgn(a.y-b.y)<0;
};
ld dot(cm a,cm b){return a.x*b.x+a.y*b.y;}
ld crs(cm a,cm b){return a.x*b.y-a.y*b.x;}
int ccw(cm a,cm b){return sgn(crs(a,b));}
int ccw(cm a,cm b,cm c){return ccw(b-a,c-a);}
//AOJ1183
int qeq(ld a,ld b,ld c,ld&d,ld&e){
	ld f=b*b-4*a*c;
	if(sgn(f)<0)return 0;
	ld g=sqrt(max(f,ld(0)));
	d=(-b+g)/(2*a);
	e=(-b-g)/(2*a);
	return sgn(f)+1;
}
//(-2)[a,-1](0)[b,1](2)
int bet(cm a,cm b,cm c){
	cm d=b-a;
	ld e=dot(d,c-a);
	if(sgn(e)<=0)return sgn(e)-1;
	return sgn(e-norm(d))+1;
}
ld tri2(cm a,cm b,cm c){
	return crs(b-a,c-a);
}
//AOJ0153
//0-no,1-edge,2-in
int cont(cm a,cm b,cm c,cm d){
	if(ccw(a,b,c)==-1)
		swap(b,c);
	return min({ccw(a,b,d),ccw(b,c,d),ccw(c,a,d)})+1;
}
//AOJ1183
//arg between ab
//assume given lengths are valid
ld arg(ld a,ld b,ld c){
	return acos(min(max((a*a+b*b-c*c)/(2*a*b),ld(-1)),ld(1)));
}

using ln=pair<cm,cm>;
cm dir(ln a){return a.b-a.a;}
cm eval(ln a,ld b){return a.a+dir(a)*b;}
cm proj(ln a,cm b){
	cm c=dir(a);
	return a.a+c*dot(c,b-a.a)/norm(c);
}
cm refl(ln a,cm b){
	return ld(2)*proj(a,b)-b;
}
//AOJ0153
ld dsp(ln a,cm b){
	cm c=proj(a,b);
	if(abs(bet(a.a,a.b,c))<=1)return abs(b-c);
	return min(abs(b-a.a),abs(b-a.b));
}
int ccw(ln a,cm b){return ccw(a.a,a.b,b);}
//AOJ1157
//0-no,1-yes(endpoint),2-yes(innner)
int iss(ln a,ln b){
	int c=ccw(a.a,a.b,b.a)*ccw(a.a,a.b,b.b);
	int d=ccw(b.a,b.b,a.a)*ccw(b.a,b.b,a.b);
	int e=max(c,d);
	if(e)return 1-e;
	int f=bet(a.a,a.b,b.a),g=bet(a.a,a.b,b.b);
	if(max(f,g)==-2||min(f,g)==2)return 0;
	return 1;
}
//AOJ1157
ld dss(ln a,ln b){
	if(iss(a,b))return 0;
	return min({dsp(a,b.a),dsp(a,b.b),dsp(b,a.a),dsp(b,a.b)});
}

using cr=pair<cm,ld>;
//AOJ0153
//0-no,1-edge,2-in
int cont(cr a,cm b){
	return sgn(a.b-abs(b-a.a))+1;
}
//AOJ0153
//0-no,1-touch,2-cross
int ids(cr a,ln b){
	return sgn(a.b-dsp(b,a.a))+1;
}
//AOJ0129 (touch以外)
//0-no(in),1-touch(in),2-cross,3-touch(out),4-no(out)
int ics(cr a,ln b){
	int c=ids(a,b);
	if(c<=1)return 4-c;
	return sgn(max(abs(b.a-a.a),abs(b.b-a.a))-a.b)+1;
}
int ccl(cr a,ln b,ld&c,ld&d){
	cm e=dir(b);
	cm f=b.a-a.a;
	return qeq(norm(e),2*dot(e,f),norm(f)-a.b*a.b,c,d);
}

//AOJ0023
//0-apart,1-coinside,2-a<b,3-a<=b,4-a>b,5-a>=b,6-a touch b,7-a cross b
int icc(cr a,cr b){
	ld c=abs(a.a-b.a);
	if(sgn(c)==0&&sgn(a.b-b.b)==0)return 1;
	int d=sgn(c+a.b-b.b);
	if(d<=0)return d+3;
	int e=sgn(c+b.b-a.b);
	if(e<=0)return e+5;
	int f=sgn(a.b+b.b-c);
	if(f>=0)return f+6;
	return 0;
}

//two intersections l,r seen be a.a
//assume two circles cross
ln ccc(cr a,cr b){
	ld c=arg(b.a-a.a);
	ld d=arg(a.b,abs(b.a-a.a),b.b);
	return ln(a.a+polar(a.b,c+d),a.a+polar(a.b,c-d));
}

//not verified
bool ips(const vc<cm>&a,ln b){
	int n=a.size();
	rep(i,n){
		cm c=a[(i+n-1)%n],d=a[i],e=a[(i+1)%n];
		if(iss(ln(c,d),b)==2)return 1;
		if(ccw(b,d)==0&&bet(b.a,b.b,d)==0){
			if(ccw(c,d,e)==1)return 1;
			if(ccw(b,c)*ccw(b,e)<0)return 1;
		}
	}
	return 0;
}

//GCJ2019R3D
//0-out,1-edge,2-in
int cont(const vc<cm>&a,cm b){
	int n=a.size();
	int res=0;
	rep(i,n){
		cm c=a[i],d=a[(i+1)%n];
		if(ccw(c,d,b)==0&&abs(bet(c,d,b))<=1)
			return 1;
		if(c.y>d.y)swap(c,d);
		if(sgn(b.y-c.y)>0&&sgn(d.y-b.y)>=0&&ccw(c,d,b)==1)
			res^=1;
	}
	return res*2;
}

ld area2(const vc<cm>&a){
	int n=a.size();
	ld b=0;
	rep(i,n)
		b+=crs(a[i],a[(i+1)%n]);
	return b;
}

//AOJ0068
//no point in edges
vc<cm> convex(vc<cm> s){
	swap(s[0],*min_element(all(s),cmcmp));
	sort(s.bg+1,s.ed,[&](cm a,cm b){
		int c=ccw(s[0],a,b);
		if(c)return c==1;
		else return bet(s[0],a,b)==2;
	});
	vc<cm> t;
	rep(i,s.size()){
		int ss;
		while((ss=t.size())>=2){
			cm a=t[ss-2];
			cm b=t[ss-1];
			cm c=s[i];
			if(ccw(a,b,c)>0)
				break;
			t.pop_back();
		}
		t.pb(s[i]);
	}
	return t;
}


cm readcm(){
	ld a,b;
	cin>>a>>b;
	return cm(a,b);
}

ld readld(){
	ld a;
	cin>>a;
	return a;
}

template<class E,class D=ll>
vc<D> dijkstra(const vvc<E>& g,int s){
	const int n=g.size();
	using P=pair<D,int>;
	priority_queue<P,vc<P>,greater<P>> pq;
	vc<D> dist(n,1e9);
	const auto ar=[&](int v,D d){
		if(dist[v]>d){
			dist[v]=d;
			pq.push(P(d,v));
		}
	};
	ar(s,0);
	while(pq.size()){
		D d;
		int v;
		tie(d,v)=pq.top();pq.pop();
		for(auto e:g[v])
			ar(e.to,d+e.cost);
	}
	return dist;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	while(1){
		int n=read();
		if(n==0)break;
		vc<cr> s(n);
		rep(i,n){
			int a=read(),b=read(),r=read();
			s[i]=cr(cm(a,b),r);
		}
		vc<cm> a;
		int to;
		{
			a.eb(s[0].a);
			rep(i,n-1){
				ln b=ccc(s[i],s[i+1]);
				//a.eb(b.a,i);
				a.eb(b.b);
			}
			to=a.size();
			a.eb(s[n-1].a);
			per(i,n-1){
				ln b=ccc(s[i],s[i+1]);
				a.eb(b.a);
				//a.eb(b.b,i);
			}
		}
		int m=a.size();
		struct E{int to;ld cost;};
		vvc<E> g(m);
		rep(i,m)rep(j,m){
			ln c(a[i],a[j]);
			if(!ips(a,c)&&cont(a,eval(c,0.5))){
				g[i].pb(E{j,abs(a[i]-a[j])});
			}
		}
		cout<<dijkstra<E,ld>(g,0)[to]<<endl;
	}
}



Measured memory_bytes: 3672