#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <numeric>
#include <sstream>
#include <complex>

using namespace std;
typedef long long ll;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

typedef long double D;
typedef complex<D> P;


const D EPS=1e-8,INF=1e12;
static constexpr D Ae=0;

template<typename T> int sig(T a,T b=0){return a<b-EPS?-1:a>b+EPS?1:0;}
template<typename T> int eq(T a,T b){return sig(abs(a-b))==0;}


D cross(const P& a, const P& b) {
	return imag(conj(a)*b);
}

D dot(const P& a, const P& b) {
	return real(conj(a)*b);
}

int ccw(const P& a, P b, P c) {
	b -= a; c -=a;
	if (cross(b, c) > 0) return 1;
	if (cross(b, c) < 0) return -1;
	if (dot(b, c) < 0) return 2;
	if (norm(b) < norm(c)) return -2;
	return 0;
}

// D pfmod(D v, D MOD) {
// 	D ret = pfmod(max(a, -a), 2*M_PI);
// 	return min(ret, 2*M_PI-ret);
// }

struct L :public vector<P>{
	L(const P& a,const P& b){
		push_back(a);push_back(b);
	}
};

bool isIntersectSS(const L&s,const L&t){
	return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1])<=0 &&
	ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1])<=0;
}

struct C{
	P o;D r;
	C(const P &o,D r):o(o),r(r){}
};

enum RELATION{INCOMPARABLE=0,SAME=1,CONTAIN=2,OVER=4};

pair<RELATION,int> cRel(const C&c1,const C&c2){
	D d=abs(c1.o-c2.o);
	if(eq(c1.o,c2.o) && eq(c1.r,c2.r)) return make_pair(SAME,1<<28);
	if(sig(d,c1.r-c2.r)<0)return make_pair(OVER,0);
	if(sig(d,c2.r-c1.r)<0)return make_pair(CONTAIN,0);
	if(sig(d,c1.r-c2.r)==0)return make_pair(OVER,1);
	if(sig(d,c2.r-c1.r)==0)return make_pair(CONTAIN,1);
	if(sig(d,c1.r+c2.r)==0)return make_pair(INCOMPARABLE,1);
	if(sig(d,c1.r+c2.r)<0)return make_pair(INCOMPARABLE,2);
	return make_pair(INCOMPARABLE,0);
}

vector<P> IntersectionCC(const C&c1,const C&c2){
	pair<RELATION,int> rel=cRel(c1,c2);
	D d=abs(c2.o-c1.o);
	P diff=(c2.o-c1.o)/d;
	vector<P> res;
	if(rel.second==1){
		res.push_back(c1.o+diff*c1.r);
	}else if(rel.second==2){
		double rc=(d*d +c1.r*c1.r-c2.r*c2.r)/(2*d);
		double rs=sqrt(c1.r*c1.r-rc*rc);
		res.push_back(c1.o+diff*P(rc,rs));
		res.push_back(c1.o+diff*P(rc,-rs));
	} 
	return res;
}





int main() {

	cout <<fixed<< setprecision(20);
	while(true){
		int n;cin >> n;if(n==0)break;

		vector<C> cs;
		REP(i,n){
			D x,y,r;cin >> x >> y >> r;
			cs.push_back(C(P(x,y),r));
		} 

		vector<P> ps;
		ps.push_back(cs[0].o);


		for(int i=0;i+1<n;i++){
			vector<P> cps=IntersectionCC(cs[i],cs[i+1]);
			REP(j,cps.size()){
				ps.push_back(cps[j]);
			}
		}
		ps.push_back(cs[cs.size()-1].o);


		vector<vector<bool>> reachable(ps.size(),vector<bool>(ps.size()));
		REP(i,ps.size())REP(j,ps.size())if(i<j){
			int ll=(i-1)/2+1,rl=(j-1)/2-1;
			if(i==0)ll=0;

			bool ok=true;
			for(int l=ll;l<=rl;l++){
				if(!isIntersectSS(L(ps[2*l+1],ps[2*l+2]),L(ps[i],ps[j]))){
					ok=false;
				}
			}
			reachable[i][j]=ok;
		}


// REP(i,ps.size())REP(j,ps.size())if(i<j){
// 	cout << i<<":"<<j<<":"<<reachable[i][j]<<endl;
// }		

		vector<D> dp(ps.size(),INF);
		dp[0]=0;
		for(int j=1;j<ps.size();j++){
			D v=INF;
			for(int i=0;i<j;i++)if(reachable[i][j]){
				v=min(v,dp[i]+abs(ps[i]-ps[j]));
			}
			dp[j]=v;
		}

		cout << dp[ps.size()-1]<<endl;
	}

	return 0;
}

Measured memory_bytes: 1360