#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; i++ )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;

const double eps=1e-6;
double add(double a,double b){
    if(abs(a+b)<eps)return 0;
    return a+b;
}

typedef pair<double,double> P;
P operator+(const P& x,const P& y){
    return {add(x.first,y.first),add(x.second,y.second)};
}

P operator-(const P& x,const P& y){
    return {add(x.first,-y.first),add(x.second,-y.second)};

}

P operator*(const P& x,const double& y){
    return {x.first*y,x.second*y};
}
double dot(P x,P y){
    return add(x.first*y.first,x.second*y.second);


}

double det(P x,P y){
    return add(x.first*y.second,-x.second*y.first);
}

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

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

bool cross(P p1,P p2,P q1,P q2){
    if(det(p1-p2,q1-q2)==0)return onseg(p1,p2,q1)||onseg(p1,p2,q2)||onseg(q1,q2,p1)||onseg(q1,q2,p2);
    P ret=intersection(p1,p2,q1,q2);
    return onseg(p1,p2,ret)&&onseg(q1,q2,ret);
}

double dist(P p1,P p2,P q){
    if(dot(q-p1,p2-p1)<=0)return sqrt(dot(q-p1,q-p1));
    if(dot(q-p2,p1-p2)<=0)return sqrt(dot(q-p2,q-p2));
    P d=p1-p2;
    P ret=q+P{d.second,-d.first};
    P h=intersection(p1, p2, q, ret);
    return sqrt(dot(q-h,q-h));
}
double d(P p,P q){
    return sqrt(dot(p-q,p-q));
}

int main(){
    int n;
    vector<int>ans;
    while(cin>>n,n!=0){
        P a[n];
        double r[n];
        rep(i,n)cin>>a[i].first>>a[i].second>>r[i];
        P b[n-1][2];
        rep(i,n-1){
            P v=(a[i+1]-a[i])*(1.0/d(a[i+1],a[i]));
            P h={v.second,-v.first};
            double l=(r[i]*r[i]+d(a[i],a[i+1])*d(a[i],a[i+1])-r[i+1]*r[i+1])/2/d(a[i],a[i+1]);
            b[i][0]=a[i]+v*l+h*sqrt(r[i]*r[i]-l*l);
            b[i][1]=a[i]+v*l-h*sqrt(r[i]*r[i]-l*l);
        }
        double x[2*n][2*n];
        rep(i,2*n)rep(j,2*n)x[i][j]=inf;
        rep(i,n-1)rep(j,2){
            bool ok=true;
            rep(k,i)if(!cross(a[0],b[i][j],b[k][0],b[k][1]))ok=false;
            if(ok)x[0][2*i+j+1]=d(a[0],b[i][j]);
        }
        rep(i,n-1)rep(j,2){
            bool ok=true;
            REP(k,i+1,n-1)if(!cross(a[n-1],b[i][j],b[k][0],b[k][1]))ok=false;
            if(ok)x[2*n-1][2*i+j+1]=d(a[n-1],b[i][j]);
        }
        rep(i,n-1)REP(j,i+1,n-1)rep(k,2)rep(l,2){
            bool ok=true;
            REP(m,i+1,j)if(!cross(b[i][k],b[j][l],b[m][0],b[m][1]))ok=false;
            if(ok)x[2*i+k+1][2*j+l+1]=d(b[i][k],b[j][l]);
        }
        bool ok=true;
        rep(i,n-1)if(!cross(a[0],a[n-1],b[i][0],b[i][1]))ok=false;
        if(ok)x[0][2*n-1]=d(a[0],a[n-1]);
        rep(i,2*n)x[i][i]=0;
        rep(i,n)x[2*i+1][2*i+2]=d(b[i][0],b[i][1]);
        rep(i,2*n)rep(j,2*n)x[i][j]=min(x[i][j],x[j][i]);
        rep(i,2*n)rep(j,2*n)rep(k,2*n)x[j][k]=min(x[i][j]+x[i][k],x[j][k]);
        cout<<setprecision(10)<<x[0][2*n-1]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3616