#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
using namespace std;
#define REP(i,n) for(int i=0; i < (n); i++)

//num
const double EPS = 1e-10;
const double INF = 1e12;
#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

// point, line, circle
typedef complex<double> P;
typedef vector<P> VP;
struct L : vector<P> {
    L(P a, P b){ push_back(a); push_back(b);}
};
struct C{
    P p;
    double r;
    C(const P& p, const double& r) : p(p), r(r) {}
};
namespace std{
    bool operator < (const P& a, const P& b){
        return (a.X != b.X)? a.X < b.X : a.Y < b.Y;
    }
}

// vector operation
double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}

//utility
int ccw(P a, P b, P c){
    b -= a;
    c -= a;
    if(cross(b,c) > EPS) return +1; //counter clockwise
    if(cross(b,c) <-EPS) return -1; //clockwise
    if(dot(b,c) < EPS) return +2; //c-a-b
    if(norm(b) < norm(c)) return -2; //a-b-c
    return 0; //a-c-b
}

VP crosspointCC(const C& a, const C& b){
    VP ps;
    P ab = b.p-a.p;
    double dist = abs(ab);
    if(GE(dist, a.r +b.r) || LE(dist, abs(a.r-b.r))){
        return ps;
    }
    if(EQ(dist, a.r+b.r)){ //circumscribed
        ps.push_back( a.p +ab*(a.r/dist) );
        return ps;
    }
    if(EQ(dist, a.r-b.r)){ //inscribed
        ps.push_back( a.p +ab*(a.r/dist) );
        return ps;
    }
    if(EQ(dist, b.r-a.r)){
        ps.push_back( b.p -ab*(b.r/dist) );
        return ps;
    }
    double l = ((a.r*a.r -b.r*b.r)/dist +dist) /2; //|am|/|ab|
    double n = sqrt(a.r*a.r -l*l);
    P mid = a.p + (ab)*(l/dist); //ab/dist: unit vector
    P hei = ab *(n/dist) *P(0,1); //orthogonal to ab
    ps.push_back(mid+hei);
    ps.push_back(mid-hei);
    return ps;
}


int main(){
    while(1){
        int n;
        cin >> n;
        if(n==0) break;
        
        vector<C> c;
        for(int i=0; i<n; i++){
            int x,y,r;
            cin >> x >> y >> r;
            c.push_back(C(P(x,y),r));
        }

        vector<vector<P> > cp(2); //0:left 1:right
        vector<P> ap;
        ap.push_back(c[0].p);
        for(int i=0; i<(int)c.size()-1; i++){
            vector<P> isp = crosspointCC(c[i], c[i+1]);
            cp[0].push_back(isp[0]);
            cp[1].push_back(isp[1]);
            ap.push_back(isp[0]);
            ap.push_back(isp[1]);
        }
        ap.push_back(c[n-1].p);

        //construct graph
        vector<vector<double> > adj(2*n, vector<double>(2*n, INF));
        for(int i=0; i<2*n; i++){
            adj[i][i]=0;
        }
        for(int s=0; s<2*n; s++){
            for(int e=s+1; e<2*n; e++){
                bool flag=true;
                for(int i=(s-1)/2; i<(e-1)/2; i++){
                    //out of leftpoints or rightpoints
                    if(ccw(ap[s], ap[e], cp[0][i])==-1 ||
                       ccw(ap[s], ap[e], cp[1][i])==+1){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    double dist = abs(ap[s]-ap[e]);
                    adj[s][e] = dist;
                    adj[e][s] = dist;
                }
            }
        }

        //search the minimum path with Dijkstra algorithm
        priority_queue<pair<double, int> > wait;
        vector<double> cost(2*n,INF);
        cost[0] = 0.0;
        wait.push(make_pair(0.0, 0));
        while(!wait.empty()){
            int nowpoint = wait.top().second;
            double nowcost = -wait.top().first;
            wait.pop();
            if(cost[nowpoint] < nowcost){
                continue;
            }
            for(int i=0; i<2*n; i++){
                double nextcost = adj[nowpoint][i] + nowcost;
                if(nextcost < cost[i]){
                    cost[i]=nextcost;
                    wait.push(make_pair(-nextcost, i));
                }
            }   
        }

        cout << fixed;
        cout << setprecision(10);
        cout << cost[2*n-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 3392