#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define show(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define show(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-6;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

typedef complex<long double> point;
typedef pair<point,point> line;
long double dot(const point& a,const point& b){ return a.real()*b.real()+a.imag()*b.imag(); }
long double cross(const point& a,const point& b){ return a.real()*b.imag()-a.imag()*b.real(); }
point polar(const long double &r, const long double &th) { return point(r*cosl(th),r*sinl(th)); }
int ccw(point a,point b,point c) {
    b-=a; c-=a;
    if(cross(b, c) > 0)   return +1;       // counter clockwise
    if(cross(b, c) < 0)   return -1;       // clockwise
    if(dot(b, c) < 0)     return +2;       // c--a--b on line
    if(norm(b) < norm(c)) return -2;       // a--b--c on line
    return 0;
}
point projection(const line& l, const point& p) {
    long double t = dot(p-l.first, l.first-l.second) / norm(l.first-l.second);
    return l.first + t*(l.first-l.second);
}
bool intersectSS(const line& s, const line& t){
    return ccw(s.first,s.second,t.first)*ccw(s.first,s.second,t.second) <= 0 &&
           ccw(t.first,t.second,s.first)*ccw(t.first,t.second,s.second) <= 0;
}

struct circle{
    point o;
    long double r;
    circle(){}
    circle(const point o,const long double r):o(o),r(r){}
};

//2??????????????????
int icc(const circle &c, const circle &d) {
    /*
      1 : intersect
      0 : distinct
      -1: c < d
      -2: c > d

      intersect or contain : true
      distinct             : false
    */
    long double od = abs((c.o-d.o));
    return c.r+d.r<od+eps ? 0 : od+c.r<d.r+eps ? -1 : od+d.r<c.r+eps ? -2 : 1;
}


//?????¨??´??????????????????
int icl(const circle &c, const line &l) {
    /*
      number of crosspoint
    */
    long double d = norm(projection(l,c.o)-c.o)-c.r*c.r;
    return d>eps ? 0 : std::abs(d)<eps ? 1 : 2;
}


//?????¨?????????????????????
int ics(const circle &c, const line &s) {
    /*
      0 : distinct
      1 : intersect 1 point
      2 : s is in c
    */
    if (!icl(c, s)) return 0;
    long double da = abs(s.first - c.o);
    long double db = abs(s.second - c.o);
    if ((da < c.r-eps) and (db < c.r-eps)) return 0;
    if ((da < c.r-eps) xor (db < c.r-eps)) return 1;
    return ccw(s.first, s.second, projection(s,c.o)) ? 0 : 2;
}

//?????¨????????????????±???????
pair<point,point> ccc(const circle &c1, const circle &c2) {
    if(!icc(c1,c2)) return pair<point,point>(c1.o,c2.o);
    long double w = abs(c2.o-c1.o), th = arg(c2.o-c1.o);
    long double dth = acosl((c1.r*c1.r+w*w-c2.r*c2.r)/(2.*c1.r*w));
    return pair<point,point>(c1.o+polar(c1.r,th-dth),c1.o+polar(c1.r,th+dth));
}

//????????´????????????
pair<point,point> ccl(const circle &c, const line &l) {
    point h = projection(l,c.o), p = sqrtl(c.r*c.r-norm(h-c.o))*(l.second-l.first)/abs(l.second-l.first);
    return pair<point,point>(h-p,h+p);
}


void solve(int n){
    vector<circle> cs;
    rep(i,0,n){
        long double x,y,r;
        cin >> x >> y >> r;
        cs.push_back(circle(point(x,y),r));
    }
    vector<point> ps;
    vector<int> idx;
    vector<line> ls;
    ps.push_back(cs[0].o);
    idx.push_back(0);
    rep(i,1,n){
        auto tmp=ccc(cs[i],cs[i-1]);
        ps.push_back(tmp.first);
        ps.push_back(tmp.second);
        idx.push_back(i-1);
        idx.push_back(i-1);
        ls.push_back(line(ps[i*2-1],ps[i*2]));
    }
    ps.push_back(cs.back().o);
    idx.push_back(n-1);

    long double dist[200][200];
    fill_n((long double*)dist,200*200,infll);
    rep(i,0,2*n) dist[i][i]=0;
    rep(i,0,2*n) rep(j,i+1,2*n) dist[i][j]=dist[j][i]=abs(ps[i]-ps[j]);
    rep(i,0,2*n) rep(j,i+1,2*n){
        line s=line(ps[i],ps[j]);
        bool f=true;
        rep(k,idx[i]+(i==0?0:1),idx[j]){
            if(intersectSS(s,ls[k])) continue;
            f=false;
            break;
        }
        if(!f) dist[i][j]=dist[j][i]=infll;
    }

    rep(k,0,2*n) rep(i,0,2*n) rep(j,0,2*n) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    cout << dist[0][2*n-1] << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    while(true){
        int n;
        cin >> n;
        if(!n) break;
        solve(n);
    }
    return 0;
}

Measured memory_bytes: 4232