#include <iostream>
#include <vector>
#include <complex>
#include <iomanip>
#include <cmath>

using namespace std;

typedef complex<double> Point;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(c) (c).begin(), (c).end()
const double eps = 1e-8, inf = 1e+8;

template<typename T> void chmin(T &t, T f){if(t > f)t = f;}
template<typename T> T sqr(T x){return x*x;}

double cross(const Point &a, const Point &b){
    return imag(conj(a) * b);
}

struct Line : vector<Point> {
    Line(const Point &a, const Point &b){
        push_back(a); push_back(b);
    }
};

bool interLS(const Line &l, const Line &s){
    return cross(l[1]-l[0], s[0]-l[0]) * cross(l[1]-l[0], s[1]-l[0]) < eps;
}

struct Circle : Point {
    double r;
    Circle(const Point &a, double r):Point(a), r(r){}
};

vector<Point> xptCC(const Circle &c1, const Circle &c2){
    vector<Point> res;
    double d = abs(c1-c2);
    if(d < eps)return res;
    double rc = (sqr(d) + sqr(c1.r) - sqr(c2.r)) / (2.*d);
    double rs = sqrt(sqr(c1.r) - sqr(rc));
    Point diff = (c2-c1) / d;
    res.push_back(c1 + diff * Point(rc, rs));
    res.push_back(c1 + diff * Point(rc, -rs));
    return res;
}

ostream& operator<<(ostream &os, const Point &a){
    return os << "(" << a.real() << ", " << a.imag() << ")";
}
#define dump(x) cerr << #x << " = " << (x) << endl;

int n;
vector<Circle> cir;
vector<vector<double> > dist;

double solve(){
    dist.assign(2*n+2, vector<double>(2*n+2, inf));
    vector<Point> ps;
    vector<Line> seg;
    rep(i, n-1){
        vector<Point> xpt(xptCC(cir[i], cir[i+1]));
        ps.insert(ps.end(), all(xpt));
        seg.emplace_back(xpt[0], xpt[1]);
        rep(j, i){
            for(auto u: {2*i, 2*i+1})for(auto v: {2*j, 2*j+1}){
                bool ok = true;
                for(int k=j; k<i; ++k){
                    if(!interLS(Line(ps[u], ps[v]), seg[k])){
                        ok = false;
                        break;
                    }
                }
                if(ok)dist[u][v] = dist[v][u] = abs(ps[u]-ps[v]);
            }
        }
    }
    //---------- v FIX ----------
    rep(i, n-1){
        for(auto u: {2*i, 2*i+1}){
            bool ok = true;
            rep(k, i){
                if(!interLS(Line(cir[0], ps[u]), seg[k])){
                    ok = false;
                    break;
                }
            }
            if(ok)dist[2*n][u] = dist[u][2*n] = abs(cir[0]-ps[u]);
        }
    }
    rep(i, n-1){
        for(auto u: {2*i, 2*i+1}){
            bool ok = true;
            for(int k=n-2; k>i; --k){
                if(!interLS(Line(cir.back(), ps[u]), seg[k])){
                    ok = false;
                    break;
                }
            }
            if(ok)dist[2*n+1][u] = dist[u][2*n+1] = abs(cir.back()-ps[u]);
        }
    }
    bool ok = true;
    rep(i, n-1)if(!interLS(Line(cir[0], cir.back()), seg[i])){
        ok = false;
        break;
    }
    if(ok)return abs(cir[0]-cir.back());
    // ---------- ^ FIX ----------
    rep(k, 2*n+2)rep(i, 2*n+2)rep(j, 2*n+2){
        chmin(dist[i][j], dist[i][k] + dist[k][j]);
    }
    return dist[2*n][2*n+1];
}

int main(){
    while(cin >> n, n){
        cir.clear();
        rep(i, n){
            int x, y, r;
            cin >> x >> y >> r;
            cir.emplace_back(Point(x, y), r);
        }
        cout << fixed << setprecision(6) << solve() << '\n';
    }
    return 0;
}

Measured memory_bytes: 1648