#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
using namespace std;

//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 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
}

void crosspointCC(const C& a, const C& b, vector<P>& ps){
    P ab = b.p-a.p;
    double dist = abs(ab);
    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);
}


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<P> cp;
        cp.push_back(c[0].p);
        for(int i=0; i<(int)c.size()-1; i++){
            crosspointCC(c[i], c[i+1], cp);
        }
        cp.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; i<e; i++){
                    if((i%2==1 && ccw(cp[s], cp[e], cp[i])==-1) ||
                       (i%2==0 && ccw(cp[s], cp[e], cp[i])==+1)){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    double dist = abs(cp[s]-cp[e]);
                    adj[s][e] = 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: 3356