#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

#define rep(i,x) for(int i = 0 ; i < x ; i ++)
#define rep1(i,x) for(int i = 1 ; i <= x ; i ++)

typedef long double ld;
const ld PI = 3.141592653589793238462643383279;

struct po{
	ld x;
	ld y;
	po(ld a){ x = a; y = 0; }
	po(ld a,ld b){ x = a; y = b; }
	po(){}
	inline ld operator()(const po& rhs) const {
		return x*rhs.x+y*rhs.y;
	}
	inline ld norm() {
		return sqrt((*this)(*this));
	}
	inline po& operator+=(const po& rhs){
		x += rhs.x;
		y += rhs.y;
		return *this;
	}
	inline po& operator-=(const po& rhs){
		x -= rhs.x;
		y -= rhs.y;
		return *this;
	}
	inline po& operator*=(const po& rhs){
		ld x_ = x*rhs.x-y*rhs.y;
		y = x*rhs.y+y*rhs.x;
		x = x_;
		return *this;
	}
	inline po& operator/=(const po& rhs){
		ld x_ = x*rhs.x+y*rhs.y;
		y = -x*rhs.y+y*rhs.x;
		x = x_;
		ld nor = rhs(rhs);
		x /= nor;
		y /= nor;
		return *this;
	}
	inline void in(){
		scanf("%Lf%Lf",&x,&y);
	}
};
inline po operator+(const po& a, const po& b){ return po(a) += b; }
inline po operator-(const po& a, const po& b){ return po(a) -= b; }
inline po operator*(const po& a, const po& b){ return po(a) *= b; }
inline po operator/(const po& a, const po& b){ return po(a) /= b; }

inline po similar(const po& a,const po& b,const po& c,const po& p,const po& q){
	return p+(q-p)*(c-a)/(b-a);
}

typedef pair<po,po> se;
#define fr first
#define sc second

struct li{
	ld a;
	ld b;
	ld c;
	li(po p,po q){
		a = q.y-p.y;
		b = p.x-q.x;
		c = p.y*q.x-p.x*q.y;
	}
	/*explicit li(se s){
		a = s.sc.y-s.fr.y;
		b = s.fr.x-s.sc.x;
		c = s.fr.y*s.sc.x-s.fr.x*s.sc.y;
		li(s.fr,s.sc);
	}*/
	li(){}
	inline ld operator()(const po& p) const {
		return a*p.x+b*p.y+c;
	}
};

void intersect(const li &l,const li &m,po* &ret){
	if(abs(l.a*m.b-m.a*l.b) <= 1e-18){
		ret = nullptr;
		return;
	}
	ret = new po;
	ret->x = -(l.c*m.b-m.c*l.b)/(l.a*m.b-m.a*l.b);
	ret->y = -(l.a*m.c-m.a*l.c)/(l.a*m.b-m.a*l.b);
}
inline bool on(const po &p,const se &s){
	return (s.fr-p)(s.sc-p) <= 1e-9;
}
void intersect(const se &s,const se &t,po* &ret){
	li l = li(s.fr,s.sc);
	li m = li(t.fr,t.sc);
	po *p;
	intersect(l,m,p);
	if(p == nullptr || (on(*p,s)&&on(*p,t)))ret = p;
	else{
		delete p;
		ret = nullptr;
	}
}
inline ld dist(const po &p,const po &q){
	return sqrt((p-q)(p-q));
}
inline li perpen(const po &p,const li &l){
	li ret;
	ret.a = l.b;
	ret.b = -l.a;
	ret.c = l.a*p.y-l.b*p.x;
	return ret;
}
inline po perpen_leg(const po &p,const li &l){
	po ret;
	li m = perpen(p,l);
	ret.x = -(l.c*m.b-m.c*l.b)/(l.a*m.b-m.a*l.b);
	ret.y = -(l.a*m.c-m.a*l.c)/(l.a*m.b-m.a*l.b);
	return ret;
}
inline ld dist(const po &p,const se &s){
	po h = perpen_leg(p,li(s.fr,s.sc));
	if(on(h,s))return dist(p,h);
	else return min( dist(p,s.fr) , dist(p,s.sc) );
}
inline ld dist(const se &s,const se &t){
	po *p;
	intersect(s,t,p);
	if(p != nullptr){
		delete p;
		return 0.0;
	}
	ld ret = min( dist(s.fr,t) , dist(s.sc,t) );
	ret = min( ret , min( dist(t.fr,s) , dist(t.sc,s) ) );
	return ret;
}
inline ld dist(const po &p, const li &l){
	return abs(l(p))/sqrt(l.a*l.a+l.b*l.b);
}

struct ci{
	po c;
	ld r;
	inline bool internal(const po &p){
		return dist(p,c) <= r+1e-9;
	}
};

ci circum(const po &p,const po &q,const po &r){
	ci ret;
	li l = perpen((p+q)/2.0,li(p,q));
	li m = perpen((q+r)/2.0,li(q,r));
	po* _c;
	intersect(l,m,_c);
	if(_c == nullptr){
		ret.c = po(0.0,0.0);
		ret.r = -1.0;
		return ret;
	}
	else {
		ret.c = *_c;
		ret.r = dist(ret.c,p);
		delete _c;
		return ret;
	}
}


void intersect(const li &l, const ci &c, po* &ret1, po* &ret2){
	ld d = dist(c.c,l);
	if(d > c.r+1e-9){
		ret1 = nullptr;
		ret2 = nullptr;
		return;
	}
	po h = perpen_leg(c.c,l);
	if(abs(d-c.r) <= 1e-9){
		ret1 = new po;
		*ret1 = h;
		ret2 = nullptr;
		return;
	}
	po v = po(l.b,-l.a);
	v /= sqrt(v(v));
	v *= sqrt(c.r*c.r-d*d);
	ret1 = new po;
	*ret1 = h+v;
	ret2 = new po;
	*ret2 = h-v;
	return;
}
void intersect(const ci &c, const ci &d, po* &ret1, po* &ret2){
	li l;
	l.a = 2*(c.c.x-d.c.x);
	l.b = 2*(c.c.y-d.c.y);
	l.c = d.c(d.c)-d.r*d.r-(c.c(c.c)-c.r*c.r);
	intersect(l,c,ret1,ret2);
}
void tangent(const po &p, const ci &c,li* &ret1,li* &ret2){
	ci d;
	d.c = (p+c.c)/2.0;
	d.r = dist(p,c.c)/2.0;
	po *q,*r;
	intersect(c,d,q,r);
	ret1 = ret2 = nullptr;
	if(q == nullptr)return;
	ret1 = new li;
	*ret1 = li(p,*q);
	delete q;
	if(r == nullptr)return;
	ret2 = new li;
	*ret2 = li(p,*r);
	delete r;
}
void cotan_in(const ci &c, const ci &d, li* &ret1, li* &ret2){
	po p = similar(-c.r,d.r,0.0,c.c,d.c);
	tangent(p,c,ret1,ret2);
}
void cotan_out(const ci &c, const ci &d, li* &ret1, li* &ret2){
	if(abs(c.r-d.r) < 1e-9){
		ret1 = new li;
		ret2 = new li;
		*ret1 = *ret2 = li(c.c,d.c);
		ret1->c += c.r*sqrt(ret1->a*ret1->a+ret1->b*ret1->b);
		ret2->c -= c.r*sqrt(ret1->a*ret1->a+ret1->b*ret1->b);
		return;
	}
	po p = similar(c.r,d.r,0.0,c.c,d.c);
	tangent(p,c,ret1,ret2);
}

int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n == 0)break;
		//cerr << "n=" << n << endl;
		ci c[102];
		rep1(i,n){
			c[i].c.in();
			scanf("%Lf",&c[i].r);
		}
		po *p[204] = {nullptr};
		p[0] = &c[1].c;
		p[1] = &c[n].c;
		int k = 2;
		rep1(i,n-1){
			intersect(c[i],c[i+1],p[k],p[k+1]);
			while(p[k] != nullptr)k ++;
		}
		/*cerr << "k=" << k << endl;
		rep(i,k){
			cerr << p[i]->x << " " << p[i]->y << endl;
		}*/
		ld d[204][204];
		rep(i,k)rep(j,k){
			if(i == j)d[i][j] = 0.0;
			else {
				vector<pair<ld,int>> vec;
				rep1(t,n){
					po *q[2];
					//if(i == 0 && j == 2)cerr << "=====================\n" << c[t].c.x << " " << c[t].c.y << " " << c[t].r << endl;
					intersect(li(*p[i],*p[j]),c[t],q[0],q[1]);
					if(q[1] != nullptr){
						ld s[2];
						/*if(i == 0 && j == 2){
							cerr << q[0]->x << " " << q[0]->y << endl;
							cerr << q[1]->x << " " << q[1]->y << endl;
						}*/
						rep(a,2)s[a] = similar(*p[i],*p[j],*q[a],0.0,1.0).x;
						if(s[0] > s[1])swap(s[0],s[1]);
						vec.push_back(pair<ld,int>(s[0]-1e-9,1));
						vec.push_back(pair<ld,int>(s[1]+1e-9,-1));
					}
					rep(a,2)if(q[a] != nullptr)delete q[a];
				}
				sort(vec.begin(),vec.end());
				int cnt = 0;
				bool ret = true;
				rep(t,vec.size()){
					/*if(i == 0 && j == 2){
						cout << vec[t].fr << " " << vec[t].sc << endl;
					}*/
					cnt += vec[t].sc;
					if(cnt == 0 && (1e-9 <= vec[t].fr && vec[t].fr <= 1.0-1e-9)
						|| (cnt == 0 && t+1 < vec.size() && 1e-9 <= vec[t+1].fr && vec[t+1].fr <= 1.0-1e-9)){
						//	cout << t << endl;
						ret = false;
					}
				}
				if(ret)d[i][j] = dist(*p[i],*p[j]);
				else d[i][j] = 10000000000.0;
			}
		}
		for(int i = 2 ; i < k ; i ++){
			//cerr << "DEBUG" << endl;
			//cerr << p[i]->x << " " << p[i]->y << endl;
			delete p[i];
		}
		/*rep(i,k)rep(j,k){
			cout << i << " " << j << " " << d[i][j] << endl;
		}*/
		rep(t,k)rep(i,k)rep(j,k){
			if(d[i][j] > d[i][t]+d[t][j]){
				d[i][j] = d[i][t]+d[t][j];
			}
		}
		printf("%.12f\n",(double)d[0][1]);
	}
}



Measured memory_bytes: 3888