#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define mp make_pair
#define pb push_back
#define EB emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr double eps = 1e-14; 
//constexpr double inf = numeric_limits<double>::max() / 10; 
constexpr double inf = 30000;
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

namespace Geometry{
    struct Point{
        double x,y;
        Point(){}
        Point(double a,double b) : x(a),y(b){}
        Point(const Point& p) : x(p.x),y(p.y){}
        Point operator + (Point p){
            return Point(x+p.x,y+p.y);
        }
        Point operator - (Point p){
            return Point(x-p.x,y-p.y);
        }
        Point operator * (double k){
            return Point(x*k,y*k);
        }
    };
    using Vector = Point;
    struct Circle{
        Point c;
        double r;
        Circle(){}
        Circle(Point p,double c) : c(p),r(c){}
        Circle(double a,double b,double c) : c(Point(a,b)) , r(c){}
    };

    // for debug
    ostream& operator<<(ostream& os,const Point& p){
        os << "{" << p.x <<"," << p.y <<"}";
        return os;
    }
    ostream& operator<<(ostream& os,const Circle& c){
        os << "{(" << c.c.x << "," << c.c.y <<")," << c.r << "}";
        return os;
    }

    // ?????????????????£??????
    Vector normalize(Vector v){
        double t = sqrt(v.x*v.x+v.y*v.y);
        return Vector(v.x/t,v.y/t);
    }

    // ?????¨???????????¢
    inline double distance(Point a,Point b){
        double x=a.x-b.x;
        double y=a.y-b.y;
        return sqrt(x*x+y*y);
    }

    // ????????????
    pair<Point,Point> getCrossPoint(Circle c1,Circle c2){
        double d = distance(c1.c,c2.c);
        Vector v = normalize(c2.c - c1.c);  // ??£????????????????????????????????????
        Vector dualv = Vector(-v.y,v.x);    // v??¨?????´???????????????
        double Cos = (c1.r*c1.r+d*d-c2.r*c2.r) / (2*c1.r*d);
        double Sin = sqrt(1-Cos*Cos);
        Point a = c1.c + v*Cos*c1.r + dualv*Sin*c1.r;
        Point b = c1.c + v*Cos*c1.r - dualv*Sin*c1.r;
        return make_pair(a,b);
    }
};

using namespace Geometry;

int N;
Circle cir[128];
double x[128],y[128],r[128];
vector<pair<Point,Point>> cross;
vector<Point> poi;
int NN;

void solve(){
    cross.assign(0,pair<Point,Point>());
    poi.assign(0,Point());
    rep(i,N){
        cin >> x[i] >> y[i] >> r[i];
        cir[i] = Circle(x[i],y[i],r[i]);
    }
    for(int i=0;i<N-1;i++){
        cross.pb(getCrossPoint(cir[i],cir[i+1]));
    }

    NN = cross.size() * 2 + 2;
    poi.push_back(Point(x[0],y[0]));
    for(int i=0;i<cross.size();i++){
        poi.push_back(cross[i].fi);
        poi.push_back(cross[i].se);
    }
    poi.push_back(Point(x[N-1],y[N-1]));

    vector<vector<double>> d(NN,vector<double>(NN,inf));
    for(int i=0;i<NN;i++) d[i][i] = 0;
    for(int i=0;i<NN;i++){
        for(int j=i+1;j<NN;j++){
            d[i][j] = d[j][i] = distance(poi[i],poi[j]);
        }
    }

    //cerr << "distance " << endl;
    //for(int i=0;i<NN;i++){
    //    for(int j=0;j<NN;j++){
    //        if(d[i][j]==inf) cerr << "inf  " << " ";
    //        else printf("%-5.3f ",d[i][j]);
    //    }
    //    cerr << endl;
    //}

    for(int i=0;i<NN;i++){
        for(int j=i+1;j<NN;j++){
            bool ok = true;
            int idx1,idx2;
            idx1 = (i%2==0) ? i+1 : i+2;
            idx2 = (j%2==1) ? j-1 : j-2;
            Vector a(poi[i]-poi[j]);
            //cout << i << " " << j << " " << idx1 <<" " << idx2 << endl;
            for(int k=idx1;k<=idx2;k+=2){
                if(k+1>idx2) break;
                Vector b(poi[k]-poi[i]);
                Vector c(poi[k+1]-poi[i]);
                double t1 = a.x*b.y - a.y*b.x;
                double t2 = a.x*c.y - a.y*c.x;
                //if(i==0 and j==7){
                //    //cout << k << " " << k+1 << " " << t1 << " " << t2 << endl;
                //}
                if(t1*t2 >= 0){
                    //cout << "NG  between " << k << " " << k+1 << endl;
                    ok=false;
                    break;
                }
            }
            if(!ok){
                d[i][j] = d[j][i] = inf;
            }
            //cerr << i << " " << j << " " << (ok? "true" : "false") << endl;
        }
    }

    /*
    cerr << "Point : " << endl;
    for(int i=0;i<NN;i++){
        cerr << i << " " << poi[i] << endl;
    }

    cerr << "distance " << endl;
    for(int i=0;i<NN;i++){
        for(int j=0;j<NN;j++){
            if(d[i][j]==inf) cerr << "inf  " << " ";
            else printf("%-5.3f ",d[i][j]);
        }
        cerr << endl;
    }
    */


    //cout << Double(d[0][5]) << " " << Double(d[5][11]) << " " << Double(d[11][13]) << " " << Double(d[13][19]) << endl; 
    //cout << d[0][11] << endl;
    /*
    cout << "0,3 : " << Double(d[0][3]) << endl;
    cout << "0,5 : " << Double(d[0][5]) << endl;
    cout << "3,5 : " << Double(d[3][5]) << endl;
    cout << "3,7 : " << Double(d[3][7]) << endl;
    cout << "5,7 : " << Double(d[5][7]) << endl;
    */



    for(int k=0;k<NN;k++){
        for(int i=0;i<NN;i++){
            for(int j=0;j<NN;j++){
                //if(abs(inf-d[i][k])<eps or abs(inf-d[k][j])<eps) continue;
                double tmp = d[i][j];
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
                //if(i==0 and j==11 and abs(tmp-d[i][j]) > eps){
                //    cout << "check :: " << k << "   "  << Double(tmp)<< " -> " << Double(d[i][j]) << endl;
                //    cout << Double(d[i][k]) << " " << Double(d[k][j]) << endl;
                //}
                //if(i==0 and j==7){
                //    cout << "0 and 7" << endl;
                //    cout <<  k << "   "  << Double(tmp)<< " -> " << Double(d[i][j]) << endl;
                //    cout << Double(d[i][k]) << " " << Double(d[k][j]) << endl;
                //}
            }
        }
    }

    //cerr << "distance " << endl;
    //for(int i=0;i<NN;i++){
    //    for(int j=0;j<NN;j++){
    //        if(abs(d[i][j]-inf) < eps) cerr << "inf  " << " ";
    //        else printf("%-5.3f ",d[i][j]);
    //    }
    //    cerr << endl;
    //}


    //cout << "0 .. 7 : " << d[0][7] << endl;
    //cout << "0..5 + 5..7 : " << d[0][5] + d[5][7] << endl;


    //cout << Double(d[0][5]) << " " << Double(d[5][11]) << " " << Double(d[11][13]) << " " << Double(d[13][19]) << endl; 

    //cout << Double(d[0][5]) << " " << Double(d[5][11]) << " " << Double(d[0][11]) << endl;
    //cout << Double(d[0][5] + d[5][11]) << endl;

    //cout << Double(d[0][5] + d[5][11] + d[11][13] + d[13][19] ) << endl;

    cout << Double(d[0][NN-1]) << endl;
}

int main(){
    while(1){
        cin >> N;
        if(N==0) break;
        solve();
    }
}

Measured memory_bytes: 3344