#include <cstdio>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
#define EPS 1e-10
#define INF 1e9

double add(double a,double b){
	if(fabs(a+b)<EPS*(fabs(a)+fabs(b)))return 0;
	return a+b;
}

class P{
public:
	double x,y,r;
	P(){}
	P(double xx,double yy,double rr){
		x=xx;
		y=yy;
		r=rr;
	}
	P operator +(P p){
		return P(add(x,p.x),add(y,p.y),r);
	}
	P operator -(P p){
		return P(add(x,-p.x),add(y,-p.y),r);
	}
	P operator *(double d){
		return P(x*d,y*d,r);
	}
	P operator /(double d){
		return P(x/d,y/d,r);
	}
	double dot(P p){
		return add(x*p.x,y*p.y);
	}
	double det(P p){
		return add(x*p.y,-y*p.x);
	}
};

bool on_seg(P p1,P p2,P q){
	return (p1-q).det(p2-q)==0 && (p1-q).dot(p2-q)<=0;
}

P intersection(P p1,P p2,P q1,P q2){
	return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}

class node{
public:
	double cost;
	int v,v2;
	node(){}
	node(double cc,int vv,int vv2){
		cost=cc;
		v=vv;
		v2=vv2;
	}
	bool operator<(const node& n1)const{
		return cost>n1.cost;
	}
};

int n;
P p[105];
P data[105][2];
double dp[105][2];

double dijk(){
	for(int i=0;i<=n;i++){
		dp[i][0]=dp[i][1]=INF;
	}
	priority_queue<node> que;
	que.push(node(0.0,0,0));
	dp[0][0]=0.0;
	while(que.size()){
		node q=que.top();
		que.pop();
		if(dp[q.v][q.v2]<q.cost)continue;
		for(int next=q.v;next<=n;next++){
			for(int j=0;j<2;j++){
				if((next==n+1 || next==0) && j==1)continue;
				bool flag=true;
				for(int k=q.v+1;k<next;k++){
					if((data[q.v][q.v2]-data[k][0]).det(data[next][j]-data[k][1])==0){
						if(!(on_seg(data[q.v][q.v2],data[k][0],data[next][j])
						  || on_seg(data[q.v][q.v2],data[k][0],data[k][1])
						  || on_seg(data[next][j],data[k][1],data[next][j])
						  || on_seg(data[next][j],data[k][1],data[k][0])))flag=false;
					}else{
						P r=intersection(data[q.v][q.v2],data[next][j],data[k][0],data[k][1]);
						if(!(on_seg(data[k][0],data[k][1],r) && on_seg(data[q.v][q.v2],data[next][j],r)))flag=false;
					}
				}
				if(flag){
					P len=data[next][j]-data[q.v][q.v2];
					double len2=sqrt(add((len.x*len.x),(len.y*len.y)));
					if(add(dp[q.v][q.v2],len2)<dp[next][j]){
						dp[next][j]=add(dp[q.v][q.v2],len2);
						que.push(node(dp[next][j],next,j));
					}
				}
			}
		}
	}
	return dp[n][0];
}

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++){
			scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].r);
		}
		data[0][0]=p[0];
		data[n][0]=p[n-1];
		for(int i=0;i<n-1;i++){
			P pp=p[i+1]-p[i];
			double len=add(pp.x*pp.x,pp.y*pp.y);
			double d=(add(p[i].r*p[i].r,-p[i+1].r*p[i+1].r)+len)/(2*sqrt(len));
			double c=sqrt(add(p[i].r*p[i].r,-d*d));
			double ang=atan2(pp.y,pp.x);
			double ang2=atan2(c,d);
			data[i+1][0]=p[i]+P(p[i].r*cos(add(ang,ang2)),p[i].r*sin(add(ang,ang2)),0);
			data[i+1][1]=p[i]+P(p[i].r*cos(add(ang,-ang2)),p[i].r*sin(add(ang,-ang2)),0);
		}
		printf("%.4f\n",dijk());
	}
	return 0;
}