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

using val_t = double;
constexpr val_t EPS = 1e-12;
using Point = complex<val_t>;
struct Line : public pair<Point, Point> {
    Line(const Point &a, const Point &b) : pair<Point, Point>(a, b) {}
};
struct Segment : public pair<Point, Point> {
    Segment(const Point &a, const Point &b) : pair<Point, Point>(a, b) {}
};
val_t dot(const Point &a, const Point &b) {
    return real(conj(a) * b);
}
val_t cross(const Point &a, const Point &b) {
    return imag(conj(a) * b);
}
val_t X(const Point &a) {
    return real(a);
}
val_t Y(const Point &a) {
    return imag(a);
}
val_t norm2(const Point &a) {
    return X(a) * X(a) + Y(a) * Y(a);
}
int sign(val_t x) {
    if (x < -EPS) return -1;
    if (x > EPS) return 1;
    return 0;
}
int ccw(const Point &a, Point b, Point c) {
    b -= a;
    c -= a;
    if (cross(b, c) > EPS) return 1;
    if (cross(b, c) < -EPS) return -1;
    if (dot(b, c) < 0) return 0;
    if (norm2(b) < norm2(c)) return 2;
    return -2;
}

bool is_crossing(const Segment &a, const Segment &b) {
    return ccw(a.first, a.second, b.first) * ccw(a.first, a.second, b.second) <= 0
    && ccw(b.first, b.second, a.first) * ccw(b.first, b.second, a.second) <= 0;
}

val_t dist2(const Point &a, const Point &b) {
    return norm2(a - b);
}

pair<Point, Point> get_isec(int x, int y, int r, int X, int Y, int R) {
    double d = hypot(abs(x - X), abs(y - Y));
    double s = (r + R + d) / 2;
    double l = 2 * sqrt(s * (s - r) * (s - R) * (s - d)) / d;
    Point ret1(x, y), ret2(x, y);
    double A = sqrt(r * r - l * l) / d;
    double B = l / d;
    Point p(X - x, Y - y), q(Y - y, -X + x);
    return make_pair(ret1 + A * p + B * q, ret2 + A * p - B * q);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<int> xs(n), ys(n), rs(n);
        for (int i = 0; i < n; i++) cin >> xs[i] >> ys[i] >> rs[i];
        int N = 2 * (n - 1);
        vector<vector<double>> dist(N + 2, vector<double>(N + 2, 1e9));
        vector<Point> isec(N);
        for (int i = 0; i < n - 1; i++) {
            pair<Point, Point> is = get_isec(xs[i], ys[i], rs[i], xs[i + 1], ys[i + 1], rs[i + 1]);
            isec[2 * i] = is.first;
            isec[2 * i + 1] = is.second;
        }

        auto ok = [&](int i, int j) -> bool {
            int I = i / 2, J = j / 2;
            if (J - I <= 1) return true;
            Segment ma(isec[i], isec[j]);
            for (int k = I + 1; k < J; k++) {
                Segment ho(isec[2 * k], isec[2 * k + 1]);
                if (is_crossing(ma, ho) == false) return false;
            }
            return true;
        };

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (ok(i, j)) {
                    dist[i][j] = dist[j][i] = sqrt(dist2(isec[i], isec[j]));
                }
            }
        }
        auto ok2 = [&](int i) -> bool {
            int I = i / 2;
            if (I == 0) return true;
            Segment ma(isec[i], Point(xs[0], ys[0]));
            for (int j = 0; j < I; j++) {
                Segment ho(isec[2 * j], isec[2 * j + 1]);
                if (is_crossing(ma, ho) == false) return false;
            }
            return true;
        };
        auto ok3 = [&](int i) -> bool {
            int I = i / 2;
            if (I == n - 2) return true;
            Segment ma(isec[i], Point(xs[n - 1], ys[n - 1]));
            for (int j = I + 1; j < n - 1; j++) {
                Segment ho(isec[2 * j], isec[2 * j + 1]);
                if (is_crossing(ma, ho) == false) return false;
            }
            return true;
        };
        for (int i = 0; i < N; i++) {
            if (ok2(i)) {
                dist[N][i] = dist[i][N] = sqrt(dist2(isec[i], Point(xs[0], ys[0])));
            }
            if (ok3(i)) {
                dist[N + 1][i] = dist[i][N + 1] = sqrt(dist2(isec[i], Point(xs[n - 1], ys[n - 1])));
            }
        }

        for (int k = 0; k < N + 2; k++) {
            for (int i = 0; i < N + 2; i++) {
                for (int j = 0; j < N + 2; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        double ans = dist[N][N + 1];
        auto ok4 = [&]() {
            Segment ma(Point(xs[0], ys[0]), Point(xs[n - 1], ys[n - 1]));
            for (int j = 0; j < n - 1; j++) {
                Segment ho(isec[2 * j], isec[2 * j + 1]);
                if (is_crossing(ma, ho) == false) return false;
            }
            return true;
        };
        if (ok4()) {
            ans = min(ans, sqrt(dist2(Point(xs[0], ys[0]), Point(xs[n - 1], ys[n - 1]))));
        }

        cout << setprecision(20) << fixed << ans << endl;
    }
}


Measured memory_bytes: 3472