#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;
namespace geom{
#define at(i) ((*this)[i])
#define pb push_back
#define X real()
#define Y imag()
#define SELF (*this)
    typedef long double R;
    typedef complex<R> P;
    const R EPS = 1e-8;
    const R PI=3.14159265358979323846264338327950288;
    enum { TRUE = 1, FALSE = 0, BORDER= -1};
    inline int sig(const R&x){return (abs(x)<EPS?0:x>0?1:-1);}
    inline int less(const R &x,const R &y){return sig(x-y)?x<y:BORDER;}
    inline R inp(const P &a,const P &b){return (conj(a)*b).X;}
    inline R outp(const P &a,const P & b){return (conj(a)*b).Y;}
    inline R norm(const P &p){return p.X*p.X+p.Y*p.Y;}
    inline P unit(const P & p){return p/abs(p);}
    inline P proj(const P &s,const P &t){return t*inp(s,t)/norm(t);}
    inline int ccw(const P &s, const P &t, const P &p, int adv = 0) {
        int res = sig(outp(t-s, p-s));
        if(res || !adv) return res;
        if(sig(inp(t-s, p-s)) < 0) return -2;
        if(sig(inp(s-t, p-t)) < 0) return 2;
        return 0;
    }
    struct L :public vector<P>{
        L(const P &p1,const P &p2){this->pb(p1);this->pb(p2);}
        L(){}
        P dir()const {return at(1)-at(0);}
        int online(const P &p) const {return !sig(outp(p-at(0),dir()));}
    };
    struct S: public L {
        S(const P &p1, const P &p2): L(p1,p2){}
        S(){}
        int online(const P &p) const{
            if(!sig(norm( p-at(0) )) || !sig(norm(p - at(1))) ) return BORDER;
            return !sig(outp(p-at(0), dir())) && inp(p-at(0), dir()) > EPS && inp(p-at(1),-dir()) > -EPS;
        }
    };
    struct C :public P{
        C(){}
        C(const P &p,const R r):P(p),r(r){}
        R r;
        int inside(const P &p)const { return less(norm(p-SELF),r*r);}
    };
    //inline P proj(const P &s,const L &t){return t[0] + proj(s-t[0], t[1]-t[0]);}

    inline int intersect (const S &s, const S &t){
        const int p = ccw(t[0], t[1], s[0], 1) * ccw(t[0], t[1], s[1], 1);
        const int q = ccw(s[0], s[1], t[0], 1) * ccw(s[0], s[1], t[1], 1);
        return (p>0 || q>0) ? FALSE : (!p || !q) ? BORDER : TRUE;
    }
    inline int intersect (const C &a,const C &b){
        return less((a.r-b.r)*(a.r-b.r),norm(a-b))+less(norm(a-b),(a.r+b.r)*(a.r+b.r))-1;
    }
    inline R dist2(const L &l,const P &p){
        return norm(outp(l.dir(),p-l[0]))/norm(l.dir());
    }
    inline int intersect(const C &c,const L &l){
        return less(dist2(l,c),c.r*c.r);
    }

    inline S crosspoint(const C &c1,const C &c2){
        if(!intersect(c1,c2)) return S();
        R d=abs(c1-c2);
        R x=(c1.r*c1.r-c2.r*c2.r+d*d)/(2*d);
        R h=sqrt(max<R>(0.,c1.r*c1.r-x*x));
        P u=unit(c2-c1);
        return S(c1+u*x+u*P(0,-1)*h,c1+u*x+u*P(0,1)*h);
    }

    // inline S crosspoint(const C &c,const L &l){
    //   R d2=dist2(l,c);
    //   if(c.r*c.r+EPS < d2) return S();
    //   P m= proj(c,l);
    //   P u = unit(l[1]-l[0]);
    //   R d=sqrt(max<R>(.0,c.r*c.r-d2));
    //   return S(m+u*d,m-u*d);
    // }

    S circlePPR(const P& a, const P& b, R r){
        return crosspoint( C(a,r), C(b,r) );
    }

    vector<L> CommonTangent(C c1,C c2){
        if(c1.r > c2.r) swap(c1,c2);
        R d=abs(c1-c2);
        vector<L> res;
        if(d<EPS) return res;
        if(d + EPS > c1.r + c2.r){
            P crs=(c1*c2.r + c2*c1.r)/(c1.r+c2.r);
            R rad = asin(c1.r/abs(crs-c1));
            res.pb(L(crs,crs+(c1-crs)*polar((R)1,rad)));
            res.pb(L(crs,crs+(c1-crs)*polar((R)1,-rad)));
        }
        if(c1.r+d+EPS > c2.r){
            R rad=0.5*PI+asin((c2.r-c1.r)/d);
            P v=unit(c2-c1)*polar((R)1,rad);
            if(c1.r+d-EPS < c2.r){
                res.pb(L(c1+v*c1.r, c1+v*c1.r+(c1-c2)*P(0,1)));
            }else{
                res.pb(L(c1+v*c1.r,c2+v*c2.r));
                v=(R)2.*proj(v,c2-c1)-v;
                res.pb(L(c1+v*c1.r,c2+v*c2.r));
            }
        }
        return res;
    }
}
using namespace geom;

R G[256][256];

int main(){
    int n;
    while(cin>>n,n){
        rep(i, 256) rep(j, 256) G[i][j] = 1e9;
        R x, y, r;
        vector<C> cs;
        vector<S> ss; 
        rep(i, n) {
            cin >> x >> y >> r;
            cs.pb(C(P(x, y), r));
        }
        ss.pb(S(cs[0], cs[0]));
        rep(i, n) {
            if(i != n-1) {
                S s = crosspoint(cs[i], cs[i+1]);
                ss.pb(s);
            } else {
                ss.pb(S(cs[n-1], cs[n-1]));
            }
            rep(j, i+1) {
                rep(k, 2) {
                    rep(l, 2) {
                        bool ok = true;
                        for(int  m = j; m < i+1; m++) {
                            if(!intersect(ss[m], S(ss[i+1][k], ss[j][l]))) {
                                ok = false;
                            }
                        }
                        if(ok) G[2*(i+1)+k][2*j+l] = G[2*j+l][2*(i+1)+k] = abs(ss[i+1][k] - ss[j][l]);
                    }
                }
            }
        }
#if 0
        rep(i, 2*n+2) {
            rep(j, 2*n+2) {
                cout << G[i][j] << " ";
            }
            cout << endl;
        }
#endif
        rep(k, 2*n+2) rep(i, 2*n+2) rep(j, 2*n+2) {
            G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
        }
        printf("%.10lf\n", (double)G[0][2*n]);
    }
    return 0;
}

Measured memory_bytes: 4312