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

typedef double D;      // ??§?¨?????????????double???long double?????????
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
typedef vector<P> VP;
const D EPS = 1e-9;    // ?¨±??????????????????????????£????????????
#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

// ?????????dot(a,b) = |a||b|cos??
D dot(P a, P b) {
  return (conj(a)*b).X;
}
// ?????????cross(a,b) = |a||b|sin??
D cross(P a, P b) {
  return (conj(a)*b).Y;
}

// ??????????????????
int ccw(P a, P b, P c) {
  b -= a;  c -= a;
  if (cross(b,c) >  EPS) return +1;  // counter clockwise
  if (cross(b,c) < -EPS) return -1;  // clockwise
  if (dot(b,c)   < -EPS) return +2;  // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line or a==b
  return 0;                          // a--c--b on line or a==c or b==c
}

// ????????¨??????
bool isecSS(P a1, P a2, P b1, P b2) {
  return ccw(a1, a2, b1)*ccw(a1, a2, b2) <= 0 &&
         ccw(b1, b2, a1)*ccw(b1, b2, a2) <= 0;
}

// 2????????????
VP crosspointCC(P a, D ar, P b, D br) {
  VP ps;
  P ab = b-a;
  D d = abs(ab);
  D crL = (norm(ab) + ar*ar - br*br) / (2*d);
  if (EQ(d, 0) || ar < abs(crL)) return ps;

  P abN = ab * P(0, sqrt(ar*ar - crL*crL) / d);
  P cp = a + crL/d * ab;
  ps.push_back(cp + abN);
  if (!EQ(norm(abN), 0)) ps.push_back(cp - abN);
  return ps;
}

D x[102], y[102], r[102];
P xy[102];

struct edge{
    int to;
    double cost;
    edge(int to, double cost) : to(to), cost(cost) {}
};

int main(){
    while(true){
        int n;
        cin >> n;
        if(n == 0) break;

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

        vector<P> points;
        points.emplace_back(x[0], y[0]);

        vector<vector<edge>> G(2*n);

        for(int i=1;i<=n;i++){
            VP crosspoints;
            if(i < n){
                crosspoints = crosspointCC(xy[i-1], r[i-1], xy[i], r[i]);
            }else{
                crosspoints.push_back(xy[n-1]);
            }
            int n_prev = points.size();
            for(P& p2 : crosspoints){
                int idx = points.size();
                points.push_back(p2);
                for(int j=0;j<n_prev;j++){
                    P& p1 = points[j];
                    int k = j % 2 == 0 ? j + 1 : j + 2;
                    bool ok = true;
                    for(;k+1<n_prev;k++){
                        if(!isecSS(p1, p2, points[k], points[k+1])){
                            ok = false;
                            break;
                        }
                    }
                    if(ok){
                        G[j].emplace_back(idx, abs(p1 - p2));
                    }
                }
            }
        }
        assert(points.size() == 2 * n);

        int N = G.size();
        vector<double> d(N, 10000000000000.0);
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> que;
        d[0] = 0;
        que.push(make_pair(0.0, 0));
        while(que.size()){
            pair<double, int> p = que.top(); que.pop();
            if(d[p.second] < p.first) continue;
            if(p.second == N-1){
                printf("%.4f\n", p.first);
                break;
            }
            for(edge e: G[p.second]){
                double nc = p.first + e.cost;
                if(d[e.to] > nc){
                    d[e.to] = nc;
                    que.push(make_pair(nc, e.to));
                }
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3364