#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);++i)
#define rep2(i,a,b) for (int i=(a);i<(b);++i)
#define rrep(i,n) for (int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;--i)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1e9;
const int mod = 1e9 + 7;
// using Graph = vector<vector<int>>;

typedef complex<double> P;
typedef vector<P> G;
#define here(g, i) g[i]
#define next(g, i) g[(i + 1) % g.size()]
#define prev(g, i) g[(i - 1 + g.size()) % g.size()]
const double EPS = 1e-10;
const double INF = 1e12;
const double PI = acos(-1);

struct L {
    P a, b, v;
    L(){}
    L(P _a, P _b) : a(_a), b(_b), v(b - a) {}
    L(double _ax, double _ay, double _bx, double _by) : L(P(_ax, _ay), P(_bx, _by)) {}
};

struct C {
    P p;
    double r;
    C(){}
    C(P _p, double _r) : p(_p), r(_r) {}
    C(double _x, double _y, double _r) : p(_x, _y), r(_r) {}
    void print() {
        cerr << p.real() << " " << p.imag() << " " << r << endl;
    }
};

C readC() {
    double x, y, r;
    cin >> x >> y >> r;
    return C(x, y, r);
}

L intersectSegmentCC(C c1, C c2) {
    P v = c2.p - c1.p;
    double ac = (norm(v) + c1.r * c1.r - c2.r * c2.r) / (2 * abs(v));
    double as = sqrt(c1.r * c1.r - ac * ac);
    P u = v / abs(v);
    P h = u * P(0, as);
    u *= ac;
    return L(c1.p + u + h, c1.p + u - h);
}

double cross(P a, P b) {
    return imag(conj(a) * b);
}

double dot(P a, P b) {
    return real(conj(a) * b);
}

int ccw(P p0, P p1, P p2) {
    if (cross(p1 - p0, p2 - p0) > 0) return +1; // counter-clockwise
    if (cross(p1 - p0, p2 - p0) < 0) return -1; // clockwise
    if (dot(p1 - p0, p2 - p0) < 0) return +2;   // online_back
    if (dot(p0 - p1, p2 - p1) < 0) return -2;   // online_front
    return 0;                                   // on_segment
}

// include endpoints
bool intersectSS(L l1, L l2) {
    return (ccw(l1.a, l1.b, l2.a) * ccw(l1.a, l1.b, l2.b) <= 0 &&
            ccw(l2.a, l2.b, l1.a) * ccw(l2.a, l2.b, l1.b) <= 0);
}

struct edge {
    int to;
    double cost;
    edge(){}
    edge(int _to, double _cost) : to(_to), cost(_cost) {}
    void print() {
        printf("{%d, %.2f}, ", to, cost);
    }
};
using Graph = vector<vector<edge>>;

// undirected
void addEdge(Graph& G, int x, int y, double c) {
    G[x].emplace_back(y, c);
    G[y].emplace_back(x, c);
}
double dijkstra(const Graph& G, int s, int g) {
    int n = G.size();
    using State = pair<double, int>;
    priority_queue<State, vector<State>, greater<State>> pq;   // cost, vertex
    vector<double> d(n, 1e18);
    d[s] = 0.;
    pq.push(make_pair(0., s));

    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int v = p.second;
        if (v == g) break;
        if (d[v] < p.first) continue;
        for (const auto& e : G[v]) {
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                pq.push(make_pair(d[e.to], e.to));
            }
        }
    }
    return d[g];
}

main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    while (cin >> n, n) {
        vector<C> circles(n);
        rep(i, n) circles[i] = readC();

        vector<L> segments(n - 1);
        const int N = 2 * n, s = N - 2, t = N - 1;
        vector<P> points(N);
        rep(i, n - 1) {
            segments[i] = intersectSegmentCC(circles[i], circles[i + 1]);
            points[2 * i] = segments[i].a;
            points[2 * i + 1] = segments[i].b;
        }
        points[s] = circles[0].p;
        points[t] = circles.back().p;

        auto canConnect = [&](int a, int b) {
            L seg(points[a], points[b]);

            int l, r; // [l, r)
            if (a == s && b == t) {
                l = 0, r = n - 1;
            }
            else if (b == s) {
                l = 0, r = a / 2;
            }
            else if (b == t) {
                l = a / 2, r = n - 1;
            }
            else {
                l = a / 2, r = b / 2;
            }

            for (int i = l; i < r; i++) {
                if (!intersectSS(seg, segments[i])) {
                    return false;
                }
            }
            return true;
        };

        Graph G(N);
        rep(i, N) {
            rep2(j, i + 1, N) {
                if (canConnect(i, j)) {
                    addEdge(G, i, j, abs(points[i] - points[j]));
                }
            }
        }

        cout << fixed << setprecision(10) << dijkstra(G, s, t) << endl;
    }
}

Measured memory_bytes: 3416