#include <iostream>
#include <complex>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef complex<double> xy;
typedef pair<double,int> P;
double eps = 1e-9;
double dot_product(xy a,xy b) {return (conj(a)*b).real();}
double cross_product(xy a,xy b) {return (conj(a)*b).imag();}
bool comp(xy a,xy b){
    return (a.real()!=b.real()? a.real()<b.real() : a.imag()<b.imag());
}

struct circle{
    int id;
    xy c;
    double r;
};

vector<xy> cc_intertsection_points(circle o1,circle o2){
    double d1 = abs(o2.c-o1.c);
    double x = (d1*d1+o1.r*o1.r-o2.r*o2.r)/(2*d1);
    xy v1 = (o2.c-o1.c)/d1,v2 = v1*(xy(0,1));
    double d2 = max(sqrt(o1.r*o1.r-x*x),0.0);
    return vector<xy> {o1.c+v1*x+v2*d2,o1.c+v1*x-v2*d2};
}

bool is_valid(xy p1,xy p2,xy q1,xy q2){
    return cross_product(p2-p1,q1-p1)*cross_product(p2-p1,q2-p1)<=eps;
}

int main(){
    int N;
    while(cin >> N && N){
        vector<circle> C;
        for(int i=0;i<N;i++){
            double x,y,r;
            cin >> x >> y >> r;
            C.push_back({i,xy(x,y),r});
        }
        vector<vector<xy>> isp,isp2;
        vector<xy> points(2*N);
        vector<vector<int>> v(2*N);
        points[0] = C[0].c;
        int id = 1;
        for(int i=0;i<N-1;i++){
            isp.push_back({cc_intertsection_points(C[i],C[i+1])});
            points[id++] = isp[i][0];
            points[id++] = isp[i][1];
        }
        points[id] = C[N-1].c;
        for(int i=0;i<N-1;i++){
            for(auto x:isp[i]){
                bool ok = true;
                for(int j=0;j<i;j++){
                    if(!is_valid(C[0].c,x,isp[j][0],isp[j][1])) ok = false;
                }
                if(ok) v[0].push_back(2*i+1+(x!=isp[i][0]));
            }
            for(auto x:isp[i]){
                bool ok = true;
                for(int j=i+1;j<N-1;j++){
                    if(!is_valid(x,C[N-1].c,isp[j][0],isp[j][1])) ok = false;
                }
                if(ok) v[2*i+1+(x!=isp[i][0])].push_back(id);
            }
        }
        bool ok = true;
        for(int i=0;i<N-1;i++){
            if(!is_valid(C[0].c,C[N-1].c,isp[i][0],isp[i][1])) ok = false;
        }
        if(ok) v[0].push_back(id);
        for(int i=0;i<N-1;i++) for(int j=i;j<N-1;j++){
            for(auto x:isp[i]){
                for(auto y:isp[j]){
                    bool ok = true;
                    for(int k=i+1;k<j;k++){
                        if(!is_valid(x,y,isp[k][0],isp[k][1])) ok = false;
                    }
                    if(ok) v[2*i+1+(x!=isp[i][0])].push_back(2*j+1+(y!=isp[j][0]));
                }
            }
        }
        vector<double> dp(2*N,1e9);
        dp[0] = 0;
        priority_queue<P,vector<P>,greater<P>> Q;
        Q.push({0,0});
        while(!Q.empty()){
            P p = Q.top(); Q.pop();
            if(dp[p.second]<p.first) continue;
            for(auto x:v[p.second]){
                double d = abs(points[p.second]-points[x]);
                if(dp[x]>p.first+d){
                    dp[x] = p.first+d;
                    Q.push({dp[x],x});
                }
            }
        }
        cout << fixed << setprecision(10) << dp[id] << endl;
    }
}


Measured memory_bytes: 3356