#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define all(x) begin(x),end(x)

#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld EPS = 1e-9;

using Real = double;
const Real PI = acos(-1);

using Point = complex<Real>;
namespace std {
    bool operator<(const Point& a, const Point& b) {
        if (a.real() == b.real()) return a.imag() < b.imag();
        return a.real() < b.real();
    }
}
struct Line {
    Point a, b;
    Line() {}
    Line(const Point& a, const Point& b) : a(a), b(b) {}
    friend ostream& operator<<(ostream& os, Line& l) {
        return os << "[" << l.a << "," << l.b << "]";
    }
};
struct Segment : Line {
    Segment() = default;

    Segment(const Point& a, const Point& b) : Line(a, b) {}
};

inline bool eq(Real a, Real b) { return abs(b - a) < EPS; }

Real radian_to_degree(Real r) {
    return r * 180.0 / PI;
}

Real degree_to_radian(Real d) {
    return d * PI / 180.0;
}

Point rotate(const Point &p, Real theta) {
    return p * polar((Real)1.0, theta);
}

Real cross(const Point& a, const Point& b) {
    return a.real() * b.imag() - a.imag() * b.real();
}

Real dot(const Point& a, const Point& b) {
    return a.real() * b.real() + a.imag() * b.imag();
}

Point projection(const Line& l, const Point& p) {
    Real A = dot(l.b - l.a, p - l.a),
            B = dot(l.a - l.b, p - l.b);
    return (A * l.b + B * l.a) / (A + B);
}

bool parallel(const Line& l1, const Line& l2) {
    return eq(cross(l1.a - l1.b, l2.a - l2.b), 0.0);
}

bool orthogonal(const Line& l1, const Line& l2) {
    return eq(dot(l1.a - l1.b, l2.a - l2.b), 0.0);
}

const int COUNTER_CLOCKWISE = 1,
        CLOCKWISE = -1,
        ONLINE_BACK = 2,
        ONLINE_FRONT = -2,
        ON_SEGMENT = 0;
int ccw(const Point& a, Point b, Point c) {
    b = b - a, c = c - a;
    if (cross(b, c) > EPS) return COUNTER_CLOCKWISE;
    if (cross(b, c) < -EPS) return CLOCKWISE;
    if (dot(b, c) < 0) return ONLINE_BACK;
    if (norm(b) < norm(c)) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool intersected(const Line& l, const Point& p) {
    return abs(ccw(l.a, l.b, p)) != 1;
}

bool intersected(const Segment& s, const Point& p) {
    return ccw(s.a, s.b, p) == 0;
}

bool intersected(const Line& l, const Segment& s) {
    return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS;
}

bool intersected(const Segment& s1, const Segment& s2) {
    return ccw(s1.a, s1.b, s2.a) * ccw(s1.a, s1.b, s2.b) <= 0 and
           ccw(s2.a, s2.b, s1.a) * ccw(s2.a, s2.b, s1.b) <= 0;
}

Real distance(const Line& l, const Point& p) {
    return abs(p - projection(l, p));
}

Real distance(const Segment& s, const Point& p) {
    Point r = projection(s, p);
    if (intersected(s, r)) return abs(r - p);
    return min(abs(s.a - p), abs(s.b - p));
}

Real distance(const Line &l, const Segment &s) {
    if (intersected(l, s)) return 0;
    return min(distance(l, s.a), distance(l, s.b));
}

Real distance(const Segment& s1, const Segment& s2) {
    if (intersected(s1, s2)) return 0.0;
    return min({ distance(s1, s2.a), distance(s1, s2.b),
                 distance(s2, s1.a), distance(s2, s1.b) });
}

Point crosspoint(const Line& l1, const Line& l2) {
    Real A = cross(l2.a - l1.a, l2.b - l1.a),
            B = cross(l2.b - l1.b, l2.a - l1.b);
    return (A * l1.b + B * l1.a) / (A + B);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    for (;;) {
        int n; cin >> n;
        if (n == 0) break;
        vector<Point> p(n);
        vector<double> r(n);
        REP(i, n) {
            double x, y; cin >> x >> y >> r[i];
            p[i] = { x, y };
        }

        vector<array<Point,2>> s(n-1);
        REP(i, n-1) {
            double d = abs(p[i+1] - p[i]);
            double a = acos((r[i]*r[i] + d*d - r[i+1]*r[i+1]) / (2 * r[i] * d));
            double t = arg(p[i+1] - p[i]);
            s[i] = { p[i] + polar(r[i], t + a),
                     p[i] + polar(r[i], t - a)};
        }

        vector<double> dist(2*n, 1e9);

        REP(i, n-1) {
            REP(k, 2) {
                bool valid = true;
                REP(j, i) {
                    if (!intersected(
                            Segment{s[j][0],s[j][1]},
                            Segment{p[0], s[i][k]})) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    chmin(dist[2 * i + k], abs(s[i][k] - p[0]));
                }
            }
        }

        REP(i, n-1) {
            REP(ik, 2) {
                FOR(j, i+1, n-1) {
                    REP(jk, 2) {
                        bool valid = true;
                        FOR(l, i+1, j) {
                            if (!intersected(
                                    Segment{ s[l][0], s[l][1] },
                                    Segment{ s[i][ik], s[j][jk] }
                                    )) {
                                valid = false;
                                break;
                            }
                        }
                        if (valid) {
                            chmin(dist[2 * j + jk], dist[2 * i + ik] + abs(s[i][ik] - s[j][jk]));
                        }
                    }
                }
            }
        }

        REP(i, n-1) {
            REP(k, 2) {
                bool valid = true;
                FOR(j, i+1, n-1) {
                    if (!intersected(
                            Segment{s[j][0],s[j][1]},
                            Segment{p[n-1], s[i][k]})) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    chmin(dist[2 * n - 1], dist[2 * i + k] + abs(s[i][k] - p[n-1]));
                }
            }
        }

        bool valid = true;
        REP(i, n-1) {
            if (!intersected(
                    Segment{s[i][0], s[i][1]},
                    Segment{p[0], p[n - 1]}
            )) {
                valid = false;
                break;
            }
        }
        if (valid) {
            chmin(dist[2 * n - 1], abs(p[0] - p[n-1]));
        }

        cout << dist[2 * n - 1] << endl;
    }

    return 0;
}



Measured memory_bytes: 3780