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

#define REP(i,n) for(int i=0; i<n; i++)

using ll = long long;
using P = complex<double>;

#define eps 1e-6

namespace std{
    template<class T> bool operator<(const complex<T> &a, const complex<T> &b) {
        return abs(a.real() - b.real()) < eps ? a.imag() + eps < b.imag() : a.real() + eps < b.real();
    }
}

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

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

bool isContainedCP(P c, double r, P a) {
    return abs(c - a) < r - eps;
}

double distanceLP(P a, P b, P c) {
    return abs(cross(b-a, c-a)) / abs(b-a);
}

double distanceSP(P a, P b, P c) {
    if (dot(b-a, c-a) < eps) return abs(c- a);
    if(dot(a-b, c-b) < eps) return abs(c - b);
    return abs(cross(b-a, c-a)) / abs(b-a);
}

bool isCrossCC(P c1, double r1, P c2, double r2) {
    double dist = abs(c1 - c2);
    return abs(r1 - r2) < dist - eps && dist + eps < r1 + r2;
}

bool isIntersectedCS(P c, double r, P a1, P a2) {
    return (!isContainedCP(c, r, a1) || !isContainedCP(c, r, a2)) &&
        distanceSP(a1, a2, c) < r - eps;
}

vector<P> getCrosspointCC(P c1, double r1, P c2, double r2) {
    double dist = abs(c1 - c2);
    double a = acos((r1 * r1 + dist * dist - r2*r2) / (2 * r1 * dist));
    return {c1 + polar(r1, arg(c2 - c1) + a), c1 + polar(r1, arg(c2 - c1) - a)};
}

vector<P> getCrosspointCS(P c, double r, P a1, P a2) {
    if(!isIntersectedCS(c, r, a1, a2)) return {};

    P base1 = a2 - a1;
    P proj = a1 + base1 * dot(c - a1, base1) / norm(base1);
    P e = (a2 - a1) / abs(a2 - a1);
    P base2 = sqrt(r * r - norm(proj - c));
    return {proj - e*base2, proj + e*base2};
}

int n;
int x[101], y[100], r[100];
P p[101];

bool isOK(int s, int t, P a, P b) {
    vector<P> vec;

    //cerr << a << " <-> " << b << endl;

    P epsV = (b - a) / abs(b - a) * 10.0 * eps;
    P a2 = a + epsV;
    P b2 = b + epsV;


    for(int i=0; i<n; i++) {
        auto res = getCrosspointCS(p[i], r[i], a2, b2);
        
        for(auto q : res)
            if(abs(abs(q-a) + abs(q - b) - abs(a-b)) < eps)
                vec.push_back(q);
    }

   // cerr << "***" << endl;
    
    bool used[101] = {};
  
    for (auto item : vec) {
        bool ok = false;
        if (abs(a - item) < eps || abs(b - item) < eps) continue;
        for (int i=0; i<n; i++) {
          bool f = isContainedCP(p[i], r[i], item);
          ok |= f;
          used[i] |= f;
        }
        if (!ok) return false;
    }

    for(int i=s+1; i<t; i++){
      if(!used[i]) return false;
    }
  
    //cerr << "OK" << endl;

    return true;
}

bool solve() {
    vector<P> points;
    vector<int> S;

    cin >> n;

    if (n == 0) return false;

    for (int i=0; i<n; i++) {
        cin >> x[i] >> y[i] >> r[i];
        p[i] = P(x[i], y[i]);
    }

    points.push_back(p[0]);
    S.push_back(0);

    for (int i=0; i<n-1; i++) {
        if (!isCrossCC(p[i], r[i], p[i+1], r[i+1])) continue;

        auto res = getCrosspointCC(p[i], r[i], p[i+1], r[i+1]);

        for (auto p : res) {
            points.push_back(p);
            S.push_back(i+1);
            //cerr << p << endl;
        }
    }

    points.push_back(p[n-1]);
    S.push_back(n-1);


    double dist[205][205];

    for(int i=0; i<points.size(); i++)
        for(int j=0; j<points.size(); j++)
            dist[i][j] = 1e32 * (i != j);

    for (int i=0; i<points.size(); i++) {
        for(int j=i+1; j<points.size(); j++) {
            if(isOK(S[i], S[j], points[i], points[j])) {
                double tmp = abs(points[i] - points[j]);
                dist[i][j] = dist[j][i] = tmp;
                //cerr << points[i] << " " << points[j] << endl;
                //cerr << i << " " << j << " : " << tmp << endl; 
            }
        }
    }

    int m = points.size();

    for(int k=0; k<m; k++) {
        for(int i=0; i<m; i++) {
            for(int j=0; j<m; j++) {
                dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
            }
        }
    }

    printf("%.10lf\n", dist[0][m-1]);

    return true;
}

int main(){
    while(solve());
    return 0;
}


Measured memory_bytes: 4024