#include  <bits/stdc++.h>
#define range(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) range(i,0,n)
using namespace std;

typedef bool B;
typedef long double D;
typedef complex<D> P;
typedef vector<P> VP;
typedef struct {P s,t;} L;
typedef vector<L> VL;
typedef struct {P c;D r;} C;
typedef vector <C> VC;

const D eps=1.0e-10;
const D pi=acos(-1.0);
template<class T> bool operator==(T a, T b){return abs(a-b)< eps;}
template<class T> bool operator< (T a, T b){return a < b-eps;}
template<class T> bool operator<=(T a, T b){return a < b+eps;}
//template<class T> int sig(T r) {return (r==0||r==-0) ? 0 : r > 0 ? 1 : -1;}
template<class T> int sig(T a,T b = 0) {return a < b ? -1 : b > a ? 1 : 0;}
#define X real()
#define Y imag()

D ip(P a, P b) {return a.X * b.X + a.Y * b.Y;}
D ep(P a, P b) {return a.X * b.Y - a.Y * b.X;}
D sq(D a) {return sqrt(max(a, (D)0));}
P vec(L l){return l.t-l.s;}
inline P input(){D x,y;cin >> x >> y; return P(x,y);}
//??\??? ???????????¬????????¨???


// ??? not verify
D toRagian(D degree){ return degree*pi/180.0;}
D ang (P p){return arg(p);}
D ang (P base, P a, P b) {return arg( (b - base) / (a - base) );} // base ??????
P rot (P base, P a, D theta){
	P tar=a-base;return base+polar(abs(tar), arg(tar)+theta );
}

// ?°???± verify AOJ CGL_1_A
P proj(P b,P p){ return b*ip(b,p)/norm(b);}
P proj(L l,P p){ return l.s+proj(vec(l),p-l.s);}
// ????°? verify AOJ CGL_1_B
P refl(L l,P p){ return proj(l,p)*D(2.0)-p; }

// ???????????? verify AOJ CGL_1_C
enum CCW{
	LEFT = 1,
	RIGHT = 2,
	BACK = 4,
	FRONT = 8,
	MID = 16,
	ON=FRONT|BACK|MID
};

inline int ccw(P base, P a, P b) {              //???a??¨???b???????????????????????????
	a -= base; b -= base;
	if (ep(a, b) > 0)
		return LEFT;    // counter clockwise
	if (ep(a, b) < 0)
		return RIGHT;   // clockwise
	if (ip(a, b) < 0)
		return BACK;    // b--base--a on line
	if (norm(a) < norm(b))
		return FRONT;   // base--a--b on line
	// otherwise
	return MID;      // base--b--a on line  a??¨b????????????????????????
}

// ?????? ??´???
// verify AOJ CGL_2_A
B iver(L a, L b) {return ip(vec(a),vec(b) )== 0.0;}
B ipar(L a, L b) {return ep(vec(a),vec(b) )== 0.0;}


// ?????¨??´?????¨????????¢??£??????????????? (s??????????????????????????§?????????????¨±?????????)
B iLL(L a,L b){return !ipar(a,b);}

B eqL(L a,L b){return !iLL(a, b) && ep(vec(a), b.s - a.s)==0;}
B iLS(L a,L b){return sig(ep(vec(a),b.s-a.s))*sig(ep(vec(a),b.t-a.s)) <= 0;}
B iLSs(L a,L b){return sig(ep(vec(a),b.s-a.s))*sig(ep(vec(a),b.t-a.s)) < 0;}

// ????????¨?????????????????????
// verify AOJ CGL_2_B
B iSS(L a,L b){
	int cwa = ccw(a.s,a.t, b.s) | ccw(a.s,a.t, b.t);
	int cwb = ccw(b.s,b.t, a.s) | ccw(b.s,b.t, a.t);
	return ((cwa | cwb) & MID) || ((cwa & cwb) == (LEFT | RIGHT));
}
B iSSs(L a,L b) {
	int cwa = ccw(a.s,a.t, b.s) | ccw(a.s,a.t, b.t);
	int cwb = ccw(b.s,b.t, a.s) | ccw(b.s,b.t, a.t);
	return (cwa & cwb) == (LEFT | RIGHT);
}

// ??????
// verify AOJ CGL_2_C
P pLL(L a,L b){ return a.s+vec(a)*ep(vec(b),b.s-a.s)/ep(vec(b),vec(a));}

// ?????¨??´???????????¢
D dLP(L l,P p){return abs( ep(vec(l),p-l.s) )/abs(vec(l));}
// ?????¨??????????????¢
D dSP(L s,P p){
	if (sig( ip( vec(s), p - s.s)) <= 0) return abs(p - s.s);
	if (sig( ip(-vec(s), p - s.t)) <= 0) return abs(p - s.t);
	return dLP(s,p);
}

// ??´?????¨??´???????????¢
D dLL(L a,L b){ return iLL(a,b)?0:dLP(a,b.s);}

// ?????¨??´?????¨????????¢??£????????¢
D dLS(L a,L b){ return iLS(a,b)?0:min(dLP(a, b.s),dLP(a, b.t));}

// ????????¨??????????????¢
// verify AOJ CGL_2_D
D dSS(L a,L b){ return iSS(a,b)?0:
	min({ dSP(a,b.s),dSP(a,b.t),dSP(b,a.s),dSP(b,a.t)});
}


// ??????????????????
inline B cmp_x(const P &a,const P &b){
	return (abs(a.X-b.X)<eps ) ?  a.Y<b.Y : a.X<b.X;
}  // base x
inline B cmp_y(const P &a,const P &b){
	return (abs(a.Y-b.Y)<eps ) ?  a.X<b.X : a.Y<b.Y;
}  // base y
inline B cmp_a(const P &a,const P &b){
	return (abs(arg(a)-arg(b))<eps ) ?  norm(a) < norm(b) : arg(a)<arg(b);
} // base arg

// ????§???¢

// ??¢???
// Verify AOJ 1100
// verify CGL_3_A
D area(VP pol){
	int n=pol.size();
	D sum=0.0;
	rep(i,n){
		D x=pol[i%n].X-pol[(i+1)%n].X;
		D y=pol[i%n].Y+pol[(i+1)%n].Y;
		sum+=x*y;
	}
	return abs(sum/2.0);
}

// ???????§???¢?????????
// verify CGL_3_B
B is_convex(VP pol){
	int n=pol.size();
	rep(i,n){
		P prev=pol[(i+n-1)%n];
		P next=pol[(i+1)%n];
		if(ccw(prev,pol[i],next)==RIGHT) return false;
	}
	return true;
}

// ????§???¢??????????????? ?????? 2 ?????? 1 ???????????? 0???(???????§???¢??????)
//verify AOJ CGL_3-C
int in_polygon(VP pol,P p){
	int n=pol.size();
	int res=0;
	rep(i,n){
		if(ccw(pol[i],pol[(i+1)%n],p)==MID)
			return 1;
		D vt=(p.Y-pol[i].Y)/(pol[(i+1)%n].Y-pol[i].Y);
		D dx=pol[(i+1)%n].X-pol[i].X;
		if((pol[i].Y<=p.Y)&&(p.Y< pol[(i+1)%n].Y)&&(p.X<pol[i].X+vt*dx))res++;
		if((pol[i].Y> p.Y)&&(p.Y>=pol[(i+1)%n].Y)&&(p.X<pol[i].X+vt*dx))res--;
	}
	return res?2:0;
}

// ????§???¢??????????????????(???????§???¢??????)
// Verify AOJ 2514

bool in_polygon(VP pol,L l){
	VP check;
	int n=pol.size();

	rep(i,n){
		L tar={pol[i],pol[(i+1)%n]};
		if(iSS(l,tar))
			check.push_back(pLL(l,tar));
	}

	check.push_back(l.s);
	check.push_back(l.t);
	sort(check.begin(),check.end(),cmp_x);
	n=check.size();
	rep(i,n-1){
		P m=(check[i]+check[i+1])/P(2.0,0.0);
		if(!in_polygon(pol,m)) return false;
	}
	return true;
}


// convex_hull
// Verify AOJ 0063
// Verify AOJ CGL_4_A
VP convex_hull(VP pol){
	int n=pol.size(),k=0;
	sort(pol.begin(),pol.end(),cmp_x);
	VP res(2*n);

	//??\??????while?????????????????????
	//????????????????????????????????????????????´??????<=0
	//???????????????????????????????????????????????´??????<0

	// down
	rep(i,n){
		while( k>1 && ep(res[k-1]-res[k-2],pol[i]-res[k-1])<0) k--;
		res[k++]=pol[i];
	}
	// up
	for(int i=n-2,t=k;i>=0;i--){
		while( k>t && ep(res[k-1]-res[k-2],pol[i]-res[k-1])<0) k--;
		res[k++]=pol[i];
	}
	res.resize(k-1);
	return res;
}

// ????????????
// verify AOJ CGL_4_C
VP convex_cut(const VP& pol, const L& l) {
	VP res;
	int n=pol.size();
	rep(i,n){
		P a = pol[i], b = pol[(i+1)%n];
		if(ccw(l.s, l.t, a) != RIGHT) res.push_back(a);
		if((ccw(l.s, l.t, a)|ccw(l.s, l.t, b))==(LEFT|RIGHT))
			res.push_back(pLL({a,b}, l));
	}
	return res;
}

// ???
// Verify AOJ 1183

enum RCC{
	A_IN_B=1,
	B_IN_A=2,
	A_ON_B=4,
	B_ON_A=8,
	ISC=16,
	ON_OUT=32,
	OUT=64,
	SAME=12,
	ONS=48
};


int rCC(C a,C b){
	D d=abs(a.c-b.c);
	int res=0;
	if(a.r+b.r< d) res|=OUT;
	if(a.r+b.r==d) res|=ON_OUT;
	if(abs(a.r-b.r) < d && d < a.r+b.r) res|=ISC;
	if(d==b.r-a.r) res|=A_ON_B;
	if(d< b.r-a.r) res|=A_IN_B;
	if(d==a.r-b.r) res|=B_ON_A;
	if(d< a.r-b.r) res|=B_IN_A;
	return res;
}

// ?????¢??£???????????????
bool iCP(C c, P p) {return sig(abs(p - c.c), c.r) <= 0;}
bool iCS(C c, L l) {return sig(c.r, dSP(l, c.c)) >= 0;}
bool iCSc(C c, L l) {return iCS(c, l) && sig(c.r, max(abs(l.s - c.c), abs(l.t - c.c))) <= 0;}

//2??????????????????
// Verify AOJ 1183

VP pCC(C a,C b){
	VP res;
	int rel=rCC(a,b);
	if(rel==SAME){   // Same
		res.push_back(a.c+P(a.r,0));
		res.push_back(a.c+P(-a.r,0));
		res.push_back(a.c+P(0,a.r));
		res.push_back(a.c+P(0,-a.r));
	}else{
		D d = abs(b.c - a.c);
		D x = (norm(d) + norm(a.r) - norm(b.r)) / (2 * d);
		P e = (b.c - a.c) / abs(b.c - a.c);
		if(rel==ISC){ // 2points
			P w = e * P(0, 1) * sq(norm(a.r)-norm(x));
			res.push_back(a.c + e * x - w);
			res.push_back(a.c + e * x + w);
		}else if(rel&ONS){ // 1points
			res.push_back(a.c + e * x);
		}
	}
	return res;
}


VP pCL(C c, L l) {
	VP res;
	P h = proj(l,c.c);
	P e = vec(l) / abs(vec(l)) * sq(norm(c.r) - norm(h - c.c));
	res.push_back(h - e);
	res.push_back(h + e);
	return res;
}


// ????????\???
// Verify AOJ 2001

L tanC(C c,D t){
	P p=c.c+polar(c.r,t);
	P d=polar(c.r,t)*P(0,1);
	return L{p-d,p+d};
}


// ????????±?????\???
// Verify AOJ 2001

VL common_tan(C a,C b){
	VL res;
	P ba=b.c-a.c;
	D d=ang(ba);
	D i=acos((a.r+b.r)/abs(ba));
	D o=acos((a.r-b.r)/abs(ba));
	int r=rCC(a,b);

	if(r==OUT){		//??±????????\???
		res.push_back(tanC(a,d+i));
		res.push_back(tanC(a,d-i));
	}

	if(r>=ISC){		// ??±????????\???
		res.push_back(tanC(a,d+o));
		res.push_back(tanC(a,d-o));
	}

	if(r&ONS) res.push_back(tanC(a,d)); //??\????????±???????????\???

	if(r==SAME) rep(i,5) res.push_back(tanC(a,i));
	return res;
}


const int vmax=1010;
struct node{int to;D cost;};
// segments arrangement
vector<node> graph[vmax];
void sArr(const vector<L> &seg, vector<P> &point){
	rep(i,seg.size()){
		point.push_back(seg[i].s);
		point.push_back(seg[i].t);
		range(j,i+1,seg.size()){
			if (iSS(seg[i],seg[j]))
				point.push_back( pLL(seg[i],seg[j]));
		}
	}
	sort(point.begin(),point.end(),cmp_x);
	point.erase(unique(point.begin(),point.end(),cmp_x), point.end());

	rep(i,seg.size()){
		vector< pair<D, int> > list;
		rep(j,point.size())
			if (ccw(seg[i].s,seg[i].t, point[j])==MID)
				list.push_back(make_pair(norm(seg[i].s-point[j]), j));
		sort(list.begin(),list.end());
		range(j,1,list.size()){
			int a = list[j-1].second, b = list[j].second;
			graph[a].push_back( {b, abs(point[a]-point[b])} );
			graph[b].push_back( {a, abs(point[a]-point[b])} );
		}
	}
}



// under not verify

// ????????????????????????
/*
vector<L> merge(vector<L> lines) {
	rep(i,lines.size())
		if(lines[i].t < lines[i].s)
			swap(lines[i].s, lines[i].t);
	sort(lines.begin(),lines.end());
	rep(i,lines.size())rep(j,i){
		if (iSS(lines[i],lines[j])&&!iSSs(lines[i],lines[j])){
			if(abs(lines[i].t-lines[j].s) > abs(vec(lines[j])))
				lines[j].t = lines[i].t;
			lines.erase(lines.begin() + i--);
			break;
		}
	}
	return lines;
}
*/

// ???????????£??¨????????°?
// ????§???¢???????????????????????????????????????
VP normalize_polygon(VP pol){
	int n=pol.size();
	rep(i,n){
		P prev=pol[(i+n-1)%n];
		P next=pol[(i+1)%n];
		if(ccw(prev,pol[i],next)==MID)
			pol.erase(pol.begin() + i--);
	}
	return pol;
}


L bisector(P a, P b) {
  P mid=(a+b)*P(0.5,0);
  return L{mid, mid+(b-a)*P(0, pi/2)};
}

VP voronoi_cell(VP pol,VP v, int s) {
  rep(i, v.size()) if(i!=s) pol = convex_cut(pol,bisector(v[s], v[i]));
  return pol;
}

using Edge = tuple<int, D>;
using State = tuple<D, int>;

const D inf = 1e30;

int main(void){
    for(int n; cin >> n, n;){
        VC circles(n);
        rep(i, n){
            circles[i].c = input();
            cin >> circles[i].r;
        }

        VP ps;
        rep(i, n - 1){
            VP cur = pCC(circles[i], circles[i + 1]);
            ps.push_back(cur[0]);
            ps.push_back(cur[1]);
        }
        ps.push_back(circles[0].c);
        ps.push_back(circles[n - 1].c);

        vector<vector<Edge>> edge(2 * n);

        // mid -> mid
        rep(i, n - 1){
            rep(j, i){
                rep(k, 2){
                    rep(l, 2){
                        int a = i * 2 + k, b = j * 2 + l;
                        L line = {ps[a], ps[b]};

                        bool ok = true;
                        range(m, j + 1, i){
                            if(not iSS(line, {ps[m * 2], ps[m * 2 + 1]})) ok = false;
                        }
                        if(ok){
                            edge[a].push_back(Edge(b, sq(ip(vec(line), vec(line)))));
                            edge[b].push_back(Edge(a, sq(ip(vec(line), vec(line)))));
                        }
                    }
                }
            }
        }

        // start -> mid
        rep(i, n - 1){
            rep(j, 2){
                int a = 2 * n - 2, b = i * 2 + j;
                L line = {ps[a], ps[b]};

                bool ok = true;
                rep(k, i){
                    if(not iSS(line, {ps[k * 2], ps[k * 2 + 1]})) ok = false;
                }
                if(ok){
                    edge[a].push_back(Edge(b, sq(ip(vec(line), vec(line)))));
                    edge[b].push_back(Edge(a, sq(ip(vec(line), vec(line)))));
                }
            }
        }

        // mid -> goal
        rep(i, n - 1){
            rep(j, 2){
                int a = i * 2 + j, b = 2 * n - 1;
                L line = {ps[a], ps[b]};

                bool ok = true;
                range(k, i + 1, n - 1){
                    if(not iSS(line, {ps[k * 2], ps[k * 2 + 1]})) ok = false;
                }
                if(ok){
                    edge[a].push_back(Edge(b, sq(ip(vec(line), vec(line)))));
                    edge[b].push_back(Edge(a, sq(ip(vec(line), vec(line)))));
                }
            }
        }

        // start -> goal
        {
            int a = 2 * n - 2, b = 2 * n - 1;
            L line = {ps[a], ps[b]};

            bool ok = true;
            rep(i, n - 1){
                if(not iSS(line, {ps[i * 2], ps[i * 2 + 1]})) ok = false;
            }
            if(ok){
                edge[a].push_back(Edge(b, sq(ip(vec(line), vec(line)))));
                edge[b].push_back(Edge(a, sq(ip(vec(line), vec(line)))));
            }
        }

        vector<D> min_dist(2 * n, inf);
        priority_queue<State, vector<State>, greater<State>> q;
        q.push(State(0.0, 2 * n - 2));

        while(q.size()){
            int v;
            D cost;
            tie(cost, v) = q.top(); q.pop();

            // cerr << v << endl;
            if(min_dist[v] != inf) continue;
            min_dist[v] = cost;

            for(auto & e : edge[v]){
                int nv;
                D dist;
                tie(nv, dist) = e;

                if(min_dist[nv] != inf) continue;
                q.push(State(cost + dist, nv));
            }
        }

        cout.precision(12);
        cout << min_dist[2 * n - 1] << endl;
    }

    return 0;
}

Measured memory_bytes: 3600