#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <complex>
#include <cmath>

using namespace std;
typedef long long ll;



typedef long double R;
typedef complex<R> P;

R ssqrt(R d) {
    d = max<R>(0, d);
    return sqrt(d);
}

R sacos(R d) {
    d = max<R>(-1, d);
    d = min<R>(1, d);
    return acos(d);
}

namespace std {
    bool operator < (P a, P b) {
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
    bool operator > (P a, P b) {
        return (b < a);
    }
}

const R EPS = 1e-10;
const R PI = acos(-1);

/*
 -1 -> neg
  0 -> near 0
  1 -> pos
  */
int sgn(R a) {
    if (a < -EPS) return -1;
    if (a > EPS) return 1;
    return 0;
}

int sgn(R a, R b) {
    return sgn(b-a);
}

bool near(P a, P b) {
    return !sgn(abs(a-b));
}

R cross(P a, P b) { return imag(conj(a)*b); }
R dot(P a, P b) { return real(conj(a)*b); }

/* 1->cclock
  -1->clock
   0->on
   2->back
  -2->front
  */
int ccw(P a, P b, P c) {
    assert(!near(a, b));
    if (near(a, c) || near(b, c)) return 0;
    int s = sgn(cross(b-a, c-a));
    if (s) return s;
    if (a > b) swap(a, b);
    if (dot(b-a, c-a) < 0) return 2;
    if (dot(a-b, c-b) < 0) return -2;
    return 0;
}

struct L {
    P x, y;
    L() {};
    L(P x, P y) :x(x), y(y) {};
};

P vec(const L &l) {
    return l.y - l.x;
}

R abs(const L &l) {
    return abs(vec(l));
}

R distLP(const L &l, const P &p) {
    return abs(cross(l.y-l.x, p-l.x)/abs(l.y-l.x));
}

//????????¨??????????°??????¢
R distSP(const L &s, const P &p) {
    R r = min(abs(s.x-p), abs(s.y-p));
    P s2 = vec(s)*P(0, 1);
    if (ccw(s.x, s.x+s2, p) == 1) return r;
    if (ccw(s.y, s.y+s2, p) == -1) return r;
    return min(r, distLP(s, p));
}

struct C {
    P p;
    R r;
    C () {};
    C (P p, R r) : p(p), r(r) {};
};

int crossSC(const L&l, const C &c) {
    R mi = distSP(l, c.p);
    if (sgn(c.r, mi) == 1) return 0;
    if (sgn(c.r, mi) == 0) return 1;
    int u = 0;
    if (sgn(c.r, abs(l.x-c.p)) != -1) u++;
    if (sgn(c.r, abs(l.y-c.p)) != -1) u++;
    return u;
}


//return number of cross point
int crossP(const C &c, const C &d, L &l) {
    if (near(c.p, d.p) && !sgn(c.r, d.r)) return -1;
    R di = abs(c.p - d.p);
    if (sgn(c.r+d.r, di) == 1) return 0;
    if (sgn(di, abs(c.r-d.r)) == 1) return 0;
    R bth = arg(d.p - c.p);
    R th = sacos((c.r*c.r + di*di - d.r*d.r) / (2*c.r*di));
    l.x = c.p+polar<R>(c.r, bth+th);
    l.y = c.p+polar<R>(c.r, bth-th);
    if (sgn(th) == 0) return 1;
    return 2;
}

bool insLS(const L &l, const L &s) {
    int a = ccw(l.x, l.y, s.x);
    int b = ccw(l.x, l.y, s.y);
    if (a == 1 && b == 1) return false;
    if (a == -1 && b == -1) return false;
    return true;
}

bool insSS(const L &s, const L &t) {
    int a = ccw(s.x,s.y,t.x), b = ccw(s.x,s.y,t.y);
    int c = ccw(t.x,t.y,s.x), d = ccw(t.x,t.y,s.y);
    if (a*b <= 0 && c*d <= 0) return true;
    return false;
}

/*
exec??§res??????????????¢?????\???
*/
const R INF = 1e9;
template<int V>
struct Dijkstra {
    typedef R T;
    typedef pair<T, int> P;
    vector<P> g[V];
    void add(int from, int to, T dist) {
        g[from].push_back(P(dist, to));
    }
    T res[V];
    void exec(int s) {
        fill_n(res, V, INF);
        priority_queue<P, vector<P>, greater<P>> q;
        q.push(P(0, s));
        res[s] = 0;
        while (!q.empty()) {
            P p = q.top(); q.pop();
            if (res[p.second] < p.first) continue;
            for (P e: g[p.second]) {
                if (p.first+e.first < res[e.second]) {
                    res[e.second] = p.first+e.first;
                    q.push(P(e.first+p.first, e.second));
                }
            }
        }
        return;
    }
};



const int MN = 110;
int n;
C c[MN];
L l[MN];

bool calc(L ll, int i, int j) {
    for (int k = i+1; k < j; k++) {
        if (!insSS(ll, l[k])) return false;
    }
    return true;
}
R solve() {
    l[0] = L(c[0].p, c[0].p);
    for (int i = 1; i < n; i++) {
        crossP(c[i-1], c[i], l[i]);
    }
    l[n] = L(c[n-1].p, c[n-1].p);
    n++;
    Dijkstra<MN*2> djk;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (calc(L(l[i].x, l[j].x), i, j)) {
                djk.add(i*2, j*2, abs(l[i].x-l[j].x));
            }
            if (calc(L(l[i].x, l[j].y), i, j)) {
                djk.add(i*2, j*2+1, abs(l[i].x-l[j].y));
            }
            if (calc(L(l[i].y, l[j].x), i, j)) {
                djk.add(i*2+1, j*2, abs(l[i].y-l[j].x));
            }
            if (calc(L(l[i].y, l[j].y), i, j)) {
                djk.add(i*2+1, j*2+1, abs(l[i].y-l[j].y));
            }
        }
    }
    djk.exec(0);
    return djk.res[2*n-1];
}


int main() {
    while (true) {
        cin >> n;
        if (!n) break;
        for (int i = 0; i < n; i++) {
            R x, y, r;
            cin >> x >> y >> r;
            c[i] = C(P(x, y), r);
        }
        printf("%.20Lf\n", (long double)solve());
    }
    return 0;
}

Measured memory_bytes: 1416