// Slower C++ solution:
#include <complex>

#include <cstdio>

#include <string>

#include <queue>

#include <iostream>

#include <vector>

#include <tuple>

using namespace std;



#define loop(i,a,b) for(int i=(a);i<int(b);i++)

#define rep(i,b) loop(i,0,b)



typedef double R;



const R eps = 1e-8;

const R inf = 1e12;

typedef complex<R> P;

namespace std {

    bool operator < (const P& a, const P& b) {

        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);

    }

}

R cross(const P& a, const P& b) {

    return imag(conj(a)*b);

}

R dot(const P& a, const P& b) {

    return real(conj(a)*b);

}



struct L : public vector<P> {

    L(const P &a = P(), const P &b = P()) {

        push_back(a); push_back(b);

    }

    // ax+by+c=0

    L(R a, R b, R c){

        if(fabs(a) < eps) *this = L(P(0,-c/b),P(1,-c/b));

        else if(fabs(b) < eps) *this = L(P(-c/a,0),P(-c/a,1));

        else *this = L(P(-c/a,0), P(0,-c/b));

    }

};



typedef vector<P> G;



struct C {

    P p; R r;

    C(const P &p, R r) : p(p), r(r) { }

    C(){}

};

bool debug = false;

struct VS {

    vector<string> ls;

    int cnt;

    double POINT_SIZE;

    double max_x, min_x, max_y, min_y;

    static char buf[2048];



    void chboundary(const C& c){

        max_x = max<double>(max_x, c.p.real() + c.r);

        max_y = max<double>(max_y, c.p.imag() + c.r);

        min_x = min<double>(min_x, c.p.real() - c.r);

        min_y = min<double>(min_y, c.p.imag() - c.r);

    }



    VS() : cnt(1), POINT_SIZE(1) { min_x = min_y = +inf; max_x = max_y = -inf; }

    VS& clear(){ return *this = VS(); }



    // 円

    VS& append(C const& c, const char* color = "black"){

        chboundary(c);

        sprintf(buf, "set object %d circle at %lf,%lf size %lf fc rgb \"%s\"",

                cnt++, (double)c.p.real(), (double)c.p.imag(), (double)c.r, color);

        ls.push_back(buf);

        return *this;

    }



    // 点

    VS& append(P const& p, const char* color = "black"){

        return append(C(p,POINT_SIZE), color);

    }



    // 多角形

    VS& append(G const& g, const char* color = "black"){

        string s;

        sprintf(buf, "set object %d polygon", cnt++);

        s += buf;

        rep(i,g.size()){

            chboundary(C(g[i],1));

            sprintf(buf, " %s %lf,%lf", i==0 ? "from" : "to",

                    (double)g[i].real(), (double)g[i].imag());

            s += buf;

        }

        sprintf(buf,

                " to %lf,%lf fc rgb \"%s\"",

                (double)g.front().real(), (double)g.front().imag(), color);

        s += buf; ls.push_back(s);

        return *this;

    }



    // 線分

    VS& append(L const& l, const char* color = "black"){

        return append(G{l[0],l[1]}, color);

    }



    // 直接入力

    VS& append(string const& s){

        ls.push_back(s); return *this;

    }



    // 出力

    VS& plot(string png_name = "plt.png"){

        if(!debug) return *this;

        FILE* fp = popen("gnuplot -persist", "w");

        // FILE* fp = stdout;

        // FILE* fp = fopen((png_name + ".plt").c_str(), "w");

        {

            double wy = max_y-min_y, wx = max_x-min_x;

            double d = abs(wy-wx);

            if(wy > wx){

                max_x += d/2; min_x -= d/2;

            } else {

                max_y += d/2; min_y -= d/2;

            }

            POINT_SIZE = 0.1;

        }

        fprintf(fp, "set size square\n");

        fprintf(fp, "set xrange [%lf:%lf]\n", min_x, max_x);

        fprintf(fp, "set yrange [%lf:%lf]\n", min_y, max_y);

        fprintf(fp, "set terminal pngcairo size 600,600\n");

        fprintf(fp, "set output \"%s\"\n", png_name.c_str());

        for(auto const& line : ls) fprintf(fp, "%s\n", line.c_str());

        fprintf(fp, "plot NaN notitle\n");

        fprintf(fp, "quit\n");

        pclose(fp);

        return *this;

    }

};

char VS::buf[2048];



VS vsualizer;



// CCW

int ccw(P a, P b, P c) {

    b -= a; c -= a;

    if (cross(b, c) > 0)   return +1; // a->b->c 反時計回り

    if (cross(b, c) < 0)   return -1; // a->b->c 時計回り

    if (dot(b, c) < 0)     return +2; // c--a--b 直線上

    if (norm(b) < norm(c)) return -2; // a--b--c 直線上

    return 0; // 2点以上が重なっている

}



// 交差判定

bool isiLL(const L &l, const L &m) {

    return

        abs(cross(l[1]-l[0], m[1]-m[0])) > eps || // non-parallel

        abs(cross(l[1]-l[0], m[0]-l[0])) < eps;   // same line

}



bool isiLS(const L &l, const L &s) {

    return

        cross(l[1]-l[0], s[0]-l[0])*       // s[0] is left of l

        cross(l[1]-l[0], s[1]-l[0]) < eps; // s[1] is right of l

}



bool isiLP(const L &l, const P &p) {

    return abs(cross(l[1]-p, l[0]-p)) < eps;

}



bool isiSS(const L &s, const L &t) {

    return

        ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&

        ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;

}



bool isiSP(const L &s, const P &p) {

    return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < eps; // triangle inequality

}



bool isiCP(const C &c, const P &p) {

    // 境界または内部

    return abs(c.p - p) <= c.r + eps;

}



int isiCC(const C& c1, const C& c2){

    double d = abs(c1.p - c2.p), r1 = c1.r, r2 = c2.r;

    if(abs(d - r1 - r2) < eps) return  1; // 接する

    if(d > r1 + r2)       return  0; // 共通部分を持たない

    if(d < r1 - r2)       return +3; // c1 が c2 の中にある

    if(d < r2 - r1)       return -3; // c2 が c1 の中にある

    return 2; // 2つの交点を持つ

}



// 射影

P proj(const L &l, const P &p) {

    double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);

    return l[0] + t*(l[0]-l[1]);

}



// 反射

P refl(const L &l, const P &p) {

    return p + 2. * (proj(l, p) - p);

}



// 距離

R dLP(const L &l, const P &p) {

    return abs(p - proj(l, p));

}



R dLL(const L &l, const L &m) {

    return isiLL(l, m) ? 0 : dLP(l, m[0]);

}



R dLS(const L &l, const L &s) {

    if (isiLS(l, s)) return 0;

    return min(dLP(l, s[0]), dLP(l, s[1]));

}



R dSP(const L &s, const P &p) {

    const P r = proj(s, p);

    if (isiSP(s, r)) return abs(r - p);

    return min(abs(s[0] - p), abs(s[1] - p));

}



R dSS(const L &s, const L &t) {

    if (isiSS(s, t)) return 0;

    return min(min(dSP(s, t[0]), dSP(s, t[1])),

               min(dSP(t, s[0]), dSP(t, s[1])));

}



R dCP(const C &c, const P &p) {

    return max(0. , abs(c.p - p));

}



// 交点

vector<P> iLL(const L &l, const L &m) {

    R A = cross(l[1] - l[0], m[1] - m[0]);

    R B = cross(l[1] - l[0], l[1] - m[0]);

    if (abs(A) < eps && abs(B) < eps) return {m[0]}; // same line

    if (abs(A) < eps) throw "PRECONDITION NOT SATISFIED!!!";

    return {m[0] + B / A * (m[1] - m[0])};

}



vector<P> iSS(const L& s, const L& t) {

    if(isiSS(s,t)) return iLL(s,t);

    else return {};

}



vector<P> iLS(const L& l, const L& s){

    if(isiLS(l,s)) return iLL(l,s);

    else return {};

}



// !!! not verified !!!

vector<P> iCL(const C& c, const L& l){

    R d = dLP(l,c.p);

    // 接する

    if(abs(d-c.r) < eps) return { proj(l, c.p) };

    // 共有点を持たない

    if(d > c.r) return {};

    P h = proj(l, c.p);

    P v = h - c.p;

    P u = v * P(0,1) * sqrt(c.r*c.r - d*d) / abs(v);

    return {h+u, h-u};

}



// !!! not verified !!!

vector<P> iCC(const C& c1, const C& c2){

    int i = isiCC(c1,c2);

    // 共通部分なし || 内部

    if(i==0 || abs(i)==3) return {};

    R r1 = c1.r, r2 = c2.r, d = abs(c1.p - c2.p);

    // 接する

    if(i==1) return { c1.p + (c2.p - c1.p) * r1/d };

    // 2つの交点

    P p = c1.p - c2.p;

    R A = -2. * p.real(), B = -2. * p.imag();

    R C = norm(c1.p) - norm(c2.p) - r1*r1 + r2*r2;

    return iCL(c1, L(A,B,C));

}



int main(){

    int n;

    int cnt = 1;

    while(cin>>n && n){

        vsualizer.clear();

        vector<C> cs(n);

        rep(i,n){

            int x,y,r;

            cin>>x>>y>>r;

            cs[i] = C(P(x,y),r);

            vsualizer.append(cs[i], "red");

        }

        vector<L> ls(n-1);

        for(int i=0;i<n-1;i++){

            auto l = iCC(cs[i],cs[i+1]);

            ls[i] = L(l[0],l[1]);

        }



        int N=n*2;

        double d[N][N];

        rep(i,N)rep(j,N){

            if(i==j)d[i][j]=0;

            else d[i][j]=inf;

        }



        L st(cs[0].p,cs[n-1].p);

        bool okst = true;

        for(int i=0;i<n-1;i++){

            auto &ps = ls[i];

            P &p1=ps[0], &p2=ps[1];

            d[i*2][i*2+1] = abs(p1-p2);

            vsualizer.append(L(p1,p2));

            if(!isiSS(st,{p1,p2})) okst=false;

            for(int j=i+1;j<n-1;j++){

                auto &qs = ls[j];

                P &q1=qs[0], &q2=qs[1];

                L s11(p1,q1), s12(p1,q2), s21(p2,q1), s22(p2,q2);

                bool ok11 = true, ok12 = true, ok21 = true, ok22 = true;

                for(int k=i+1;k<=j-1;k++){

                    auto &rs = ls[k];

                    L s(rs[0],rs[1]);

                    if(!isiSS(s,s11))ok11=false;

                    if(!isiSS(s,s12))ok12=false;

                    if(!isiSS(s,s21))ok21=false;

                    if(!isiSS(s,s22))ok22=false;

                }

                if(ok11){

                    d[i*2][j*2] = d[j*2][i*2] = abs(p1-q1);

                    vsualizer.append(L(p1,q1));

                }

                if(ok12){

                    d[i*2][j*2+1] = d[j*2+1][i*2] = abs(p1-q2);

                    vsualizer.append(L(p1,q2));

                }

                if(ok21){

                    d[i*2+1][j*2] = d[j*2][i*2+1] = abs(p2-q1);

                    vsualizer.append(L(p2,q1));

                }

                if(ok22){

                    d[i*2+1][j*2+1] = d[j*2+1][i*2+1] = abs(p2-q2);

                    vsualizer.append(L(p2,q2));

                }

            }



            L s1(ps[0],cs[0].p);

            L s2(ps[1],cs[0].p);

            bool oks1 = true, oks2 = true;

            for(int j=0;j<i;j++){

                auto &t = ls[j];

                L s(t[0],t[1]);

                if(!isiSS(s,s1)) oks1 = false;

                if(!isiSS(s,s2)) oks2 = false;

            }

            if(oks1){

                d[N-1][i*2] = d[i*2][N-1] = abs(s1[0]-s1[1]);

                vsualizer.append(s1);

            }

            if(oks2){

                d[N-1][i*2+1] = d[i*2+1][N-1] = abs(s2[0]-s2[1]);

                vsualizer.append(s2);

            }

            L t1(ps[0],cs[n-1].p);

            L t2(ps[1],cs[n-1].p);

            bool okt1 = true, okt2 = true;

            for(int j=i+1;j<n-1;j++){

                auto t = ls[j];

                L s(t[0],t[1]);

                if(!isiSS(s,t1)) okt1 = false;

                if(!isiSS(s,t2)) okt2 = false;

            }

            if(okt1){

                d[N-2][i*2] = d[i*2][N-2] = abs(t1[0]-t1[1]);

                vsualizer.append(t1);

            }

            if(okt2){

                d[N-2][i*2+1] = d[i*2+1][N-2] = abs(t2[0]-t2[1]);

                vsualizer.append(t2);

            }

        }

        if(okst){

            d[N-1][N-2] = d[N-2][N-1] = abs(st[0]-st[1]);

            vsualizer.append(st);

        }

        rep(k,N)rep(i,N)rep(j,N)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

        printf("%.4lf\n",d[N-1][N-2]);



        string name = "pCase" + to_string(cnt++) + ".png";

        vsualizer.plot(name);

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.9571792190766706x):
#include <complex>

#include <cstdio>

#include <string>

#include <iostream>

#include <vector>

using namespace std;



#define loop(i,a,b) for(int i=(a);i<int(b);i++)

#define rep(i,b) loop(i,0,b)



typedef double R;



const R eps = 1e-8;

const R inf = 1e12;

typedef complex<R> P;

namespace std {

    bool operator < (const P& a, const P& b) {

        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);

    }

}

R cross(const P& a, const P& b) {

    return imag(conj(a)*b);

}

R dot(const P& a, const P& b) {

    return real(conj(a)*b);

}



struct L : public vector<P> {

    L(const P &a = P(), const P &b = P()) {

        push_back(a); push_back(b);

    }

    // ax+by+c=0

    L(R a, R b, R c){

        if(fabs(a) < eps) *this = L(P(0,-c/b),P(1,-c/b));

        else if(fabs(b) < eps) *this = L(P(-c/a,0),P(-c/a,1));

        else *this = L(P(-c/a,0), P(0,-c/b));

    }

};



typedef vector<P> G;



struct C {

    P p; R r;

    C(const P &p, R r) : p(p), r(r) { }

    C(){}

};



// CCW

int ccw(P a, P b, P c) {

    b -= a; c -= a;

    if (cross(b, c) > 0)   return +1; // a->b->c 反時計回り

    if (cross(b, c) < 0)   return -1; // a->b->c 時計回り

    if (dot(b, c) < 0)     return +2; // c--a--b 直線上

    if (norm(b) < norm(c)) return -2; // a--b--c 直線上

    return 0; // 2点以上が重なっている

}



// 交差判定

bool isiLL(const L &l, const L &m) {

    return

        abs(cross(l[1]-l[0], m[1]-m[0])) > eps || // non-parallel

        abs(cross(l[1]-l[0], m[0]-l[0])) < eps;   // same line

}



bool isiLS(const L &l, const L &s) {

    return

        cross(l[1]-l[0], s[0]-l[0])*       // s[0] is left of l

        cross(l[1]-l[0], s[1]-l[0]) < eps; // s[1] is right of l

}



bool isiLP(const L &l, const P &p) {

    return abs(cross(l[1]-p, l[0]-p)) < eps;

}



bool isiSS(const L &s, const L &t) {

    return

        ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&

        ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;

}



bool isiSP(const L &s, const P &p) {

    return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < eps; // triangle inequality

}



bool isiCP(const C &c, const P &p) {

    // 境界または内部

    return abs(c.p - p) <= c.r + eps;

}



int isiCC(const C& c1, const C& c2){

    double d = abs(c1.p - c2.p), r1 = c1.r, r2 = c2.r;

    if(abs(d - r1 - r2) < eps) return  1; // 接する

    if(d > r1 + r2)       return  0; // 共通部分を持たない

    if(d < r1 - r2)       return +3; // c1 が c2 の中にある

    if(d < r2 - r1)       return -3; // c2 が c1 の中にある

    return 2; // 2つの交点を持つ

}



// 射影

P proj(const L &l, const P &p) {

    double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);

    return l[0] + t*(l[0]-l[1]);

}



// 反射

P refl(const L &l, const P &p) {

    return p + 2. * (proj(l, p) - p);

}



// 距離

R dLP(const L &l, const P &p) {

    return abs(p - proj(l, p));

}



R dLL(const L &l, const L &m) {

    return isiLL(l, m) ? 0 : dLP(l, m[0]);

}



R dLS(const L &l, const L &s) {

    if (isiLS(l, s)) return 0;

    return min(dLP(l, s[0]), dLP(l, s[1]));

}



R dSP(const L &s, const P &p) {

    const P r = proj(s, p);

    if (isiSP(s, r)) return abs(r - p);

    return min(abs(s[0] - p), abs(s[1] - p));

}



R dSS(const L &s, const L &t) {

    if (isiSS(s, t)) return 0;

    return min(min(dSP(s, t[0]), dSP(s, t[1])),

               min(dSP(t, s[0]), dSP(t, s[1])));

}



R dCP(const C &c, const P &p) {

    return max(0. , abs(c.p - p));

}



// 交点

vector<P> iLL(const L &l, const L &m) {

    R A = cross(l[1] - l[0], m[1] - m[0]);

    R B = cross(l[1] - l[0], l[1] - m[0]);

    if (abs(A) < eps && abs(B) < eps) return {m[0]}; // same line

    if (abs(A) < eps) throw "PRECONDITION NOT SATISFIED!!!";

    return {m[0] + B / A * (m[1] - m[0])};

}



vector<P> iSS(const L& s, const L& t) {

    if(isiSS(s,t)) return iLL(s,t);

    else return {};

}



vector<P> iLS(const L& l, const L& s){

    if(isiLS(l,s)) return iLL(l,s);

    else return {};

}



// !!! not verified !!!

vector<P> iCL(const C& c, const L& l){

    R d = dLP(l,c.p);

    // 接する

    if(abs(d-c.r) < eps) return { proj(l, c.p) };

    // 共有点を持たない

    if(d > c.r) return {};

    P h = proj(l, c.p);

    P v = h - c.p;

    P u = v * P(0,1) * sqrt(c.r*c.r - d*d) / abs(v);

    return {h+u, h-u};

}



// !!! not verified !!!

vector<P> iCC(const C& c1, const C& c2){

    int i = isiCC(c1,c2);

    // 共通部分なし || 内部

    if(i==0 || abs(i)==3) return {};

    R r1 = c1.r, r2 = c2.r, d = abs(c1.p - c2.p);

    // 接する

    if(i==1) return { c1.p + (c2.p - c1.p) * r1/d };

    // 2つの交点

    P p = c1.p - c2.p;

    R A = -2. * p.real(), B = -2. * p.imag();

    R C = norm(c1.p) - norm(c2.p) - r1*r1 + r2*r2;

    return iCL(c1, L(A,B,C));

}



int main(){

    int n;

    int cnt = 1;

    while(cin>>n && n){

        vector<C> cs(n);

        rep(i,n){

            int x,y,r;

            cin>>x>>y>>r;

            cs[i] = C(P(x,y),r);

        }

        vector<L> ls(n-1);

        rep(i,n-1){

            auto l = iCC(cs[i],cs[i+1]);

            ls[i] = L(l[0],l[1]);

        }



        int N=n*2;

        double d[N][N];

        rep(i,N)rep(j,N){

            if(i==j)d[i][j]=0;

            else d[i][j]=inf;

        }



        L st(cs[0].p,cs[n-1].p);

        bool okst = true;

        for(int i=0;i<n-1;i++){

            auto &ps = ls[i];

            P &p1=ps[0], &p2=ps[1];

            d[i*2][i*2+1] = abs(p1-p2);

            if(!isiSS(st,{p1,p2})) okst=false;

            for(int j=i+1;j<n-1;j++){

                auto &qs = ls[j];

                P &q1=qs[0], &q2=qs[1];

                L s11(p1,q1), s12(p1,q2), s21(p2,q1), s22(p2,q2);

                bool ok11 = true, ok12 = true, ok21 = true, ok22 = true;

                for(int k=i+1;k<=j-1;k++){

                    auto &rs = ls[k];

                    L s(rs[0],rs[1]);

                    if(!isiSS(s,s11))ok11=false;

                    if(!isiSS(s,s12))ok12=false;

                    if(!isiSS(s,s21))ok21=false;

                    if(!isiSS(s,s22))ok22=false;

                }

                if(ok11)d[i*2][j*2] = d[j*2][i*2] = abs(p1-q1);

                if(ok12)d[i*2][j*2+1] = d[j*2+1][i*2] = abs(p1-q2);

                if(ok21)d[i*2+1][j*2] = d[j*2][i*2+1] = abs(p2-q1);

                if(ok22)d[i*2+1][j*2+1] = d[j*2+1][i*2+1] = abs(p2-q2);

            }

            L s1(ps[0],cs[0].p);

            L s2(ps[1],cs[0].p);

            bool oks1 = true, oks2 = true;

            for(int j=0;j<i;j++){

                auto &t = ls[j];

                L s(t[0],t[1]);

                if(!isiSS(s,s1)) oks1 = false;

                if(!isiSS(s,s2)) oks2 = false;

            }

            if(oks1)d[N-1][i*2] = d[i*2][N-1] = abs(s1[0]-s1[1]);

            if(oks2)d[N-1][i*2+1] = d[i*2+1][N-1] = abs(s2[0]-s2[1]);

            L t1(ps[0],cs[n-1].p);

            L t2(ps[1],cs[n-1].p);

            bool okt1 = true, okt2 = true;

            for(int j=i+1;j<n-1;j++){

                auto t = ls[j];

                L s(t[0],t[1]);

                if(!isiSS(s,t1)) okt1 = false;

                if(!isiSS(s,t2)) okt2 = false;

            }

            if(okt1)d[N-2][i*2] = d[i*2][N-2] = abs(t1[0]-t1[1]);

            if(okt2)d[N-2][i*2+1] = d[i*2+1][N-2] = abs(t2[0]-t2[1]);

        }

        if(okst)d[N-1][N-2] = d[N-2][N-1] = abs(st[0]-st[1]);

        rep(k,N)rep(i,N)rep(j,N)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

        printf("%.4lf\n",d[N-1][N-2]);



        string name = "pCase" + to_string(cnt++) + ".png";

    }

}