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

using ld = long double;

constexpr ld eps = 1e-8;

namespace geometry2d {


using point = std::complex<long double>;

bool eq(long double a, long double b) {
    return (std::abs(a-b) < eps);
}


long double dot(point a, point b) {
    return std::real(std::conj(a) * b);
}

long double cross(point a, point b) {
    return std::imag(std::conj(a) * b);
}


class segment {
public:
    segment()
        : a(point(0, 0)),
          b(point(0, 0))
    {}
    segment(point a_, point b_)
        : a(a_), b(b_)
    {}

    point a, b;
};

class line {
public:
    line()
        : a(point(0, 0)), b(point(0, 0))
    {}
    line(point a_, point b_)
        : a(a_), b(b_)
    {}
    line(segment s)
        : a(s.a), b(s.b)
    {}

    point a, b;
};

class circle {
public:
    circle()
        : p(point(0, 0)), r(0)
    {}
    circle(point p_, long double r_)
        : p(p_), r(r_)
    {}

    point p;
    long double r;
};


int ccw(point a, point b, point c) {
    b -= a; c -= a;
    if(cross(b, c) > eps)           return 1;  // a -> b -> c : counterclockwise
    if(cross(b, c) < -eps)          return -1; // a -> b -> c : clockwise
    if(dot(b, c) < 0)               return 2;  // c -> a -> b : line
    if(std::norm(b) < std::norm(c)) return -2; // a -> b -> c : line
    return 0;                                  // a -> c -> b : line
}


bool isis_ll(line l, line m) {
    return !eq(cross(l.b - l.a, m.b - m.a), 0);
}

bool isis_ls(line l, segment s) {
    return (cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - s.a) < eps);
}

bool isis_lp(line l, point p) {
    return (std::abs(cross(l.b - p, l.a - p)) < eps);
}

bool isis_sp(segment s, point p) {
    return (std::abs(s.a - p) + std::abs(s.b - p) - std::abs(s.b - s.a) < eps);
}

bool isis_ss(segment s, segment t) {
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0
        && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}


point proj(line l, point p) {
    long double t = dot(p - l.a, l.a - l.b) / std::norm(l.a - l.b);
    return l.a + t * (l.a - l.b);
}

point is_ll(line s, line t) {
    point sv = s.b - s.a, tv = t.b - t.a;
    assert(cross(sv, tv) != 0);
    return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

long double dist_lp(line l, point p) {
    return std::abs(p - proj(l, p));
}

long double dist_ll(line l, line m) {
    return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}

long double dist_ls(line l, segment s) {
    return isis_ls(l, s) ? 0 : std::min(dist_lp(l, s.a), dist_lp(l, s.b));
}

long double dist_sp(segment s, point p) {
    point r = proj(line(s), p);
    return isis_sp(s, r) ? std::abs(r - p) : std::min(std::abs(s.a - p), std::abs(s.b - p));
}

long double dist_ss(segment s, segment t) {
    if(isis_ss(s, t)) return 0;
    long double d1 = std::min(dist_sp(s, t.a), dist_sp(s, t.b));
    long double d2 = std::min(dist_sp(t, s.a), dist_sp(t, s.b));
    return std::min(d1, d2);
}


std::vector<point> is_cc(circle const& c1, circle const& c2) {
    std::vector<point> res;
    long double d = std::abs(c1.p - c2.p);
    long double rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
    long double dfr = c1.r * c1.r - rc * rc;
    if(std::abs(dfr) < eps) {
        dfr = 0.0;
    } else if(dfr < 0.0) {
        return res;
    }

    long double rs = std::sqrt(dfr);
    point diff = (c2.p - c1.p) / d;
    res.push_back(c1.p + diff * point(rc, rs));
    if(dfr != 0.0) {
        res.push_back(c1.p + diff * point(rc, -rs));
    }
    return res;
}


} // namespace geometry2d

using namespace geometry2d;

struct edge {
    int to;
    ld cost;
};

using edges = vector<edge>;
using graph = vector<edges>;

int main() {
    int n;
    while(cin >> n, n) {
        vector<circle> cs;
        vector<point> ps;
        for(int i=0; i<n; ++i) {
            ld x, y, r;
            cin >> x >> y >> r;
            cs.emplace_back(point(x, y), r);
        }
        ps.push_back(cs[0].p);
        for(int i=0; i<n-1; ++i) {
            auto cps = is_cc(cs[i], cs[i+1]);
            if(ccw(cs[i].p, cs[i+1].p, cps[0]) == -1) {
                swap(cps[0], cps[1]);
            }
            for(auto& cp : cps) {
                ps.push_back(move(cp));
            }
        }
        ps.push_back(cs[n-1].p);
        const int N = ps.size();
        graph g(N);
        for(int i=0; i<N; ++i) {
            for(int j=i+1; j<N; ++j) {
                bool ok = true;
                int idx1, idx2;
                if(i % 2 == 1) {
                    idx1 = i+2;
                } else {
                    idx1 = i+1;
                }
                if(j % 2 == 0) {
                    idx2 = j-1;
                } else {
                    idx2 = j;
                }
                for(int k=idx1; k<idx2; k+=2) {
                    if(ccw(ps[i], ps[j], ps[k]) == -1 || ccw(ps[i], ps[j], ps[k+1]) == 1) {
                        ok = false;
                        break;
                    }
                }
                if(ok) {
                    ld dist = abs(ps[i] - ps[j]);
                    g[i].push_back((edge){j, dist});
                    g[j].push_back((edge){i, dist});
                }
            }
        }
        vector<ld> d(N, 1e18);
        d[0] = 0;
        using P = pair<ld, int>;
        priority_queue<P, vector<P>, greater<P>> que;
        que.push(make_pair(0, 0));
        while(!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if(d[v] < p.first) {
                continue;
            }
            for(auto& e : g[v]) {
                if(d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(make_pair(d[e.to], e.to));
                }
            }
        }
        cout << fixed << setprecision(10) << d[N-1] << endl;
    }
}


Measured memory_bytes: 3408