#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
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)

#define inf 1e9

D dot(P a, P b){
  return (conj(a)*b).X;
}

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;
  if(cross(b, c) < -EPS) return -1;
  if(dot(b, c) < -EPS) return +2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

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;
}

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;
}

int main(){
  while(1){
    int N, i, j, k, l, m, f;
    scanf("%d", &N);
    if(N == 0){
      return 0;
    }
    VP cs(N);
    vector<D> r(N);
    for(i = 0; i < N; i++){
      D x, y;
      scanf("%lf%lf%lf", &x, &y, &r[i]);
      cs[i] = P(x, y);
    }
    VP vs(2 * N);
    for(i = 0; i < N - 1; i++){
      VP sub = crosspointCC(cs[i], r[i], cs[i + 1], r[i + 1]);
      vs[2 * i] = sub[0];
      vs[2 * i + 1] = sub[1];
    }
    vs[2 * N - 2] = cs[0];
    vs[2 * N - 1] = cs[N - 1];
    vector<vector<D>> dis(2 * N, vector<D>(2 * N, inf));
    for(i = 0; i < N - 1; i++){
      dis[2 * i][2 * i + 1] = abs(vs[2 * i] - vs[2 * i + 1]);
      dis[2 * i + 1][2 * i] = abs(vs[2 * i] - vs[2 * i + 1]);
      for(j = i + 1; j < N - 1; j++){
        for(k = 0; k < 2; k++){
          for(l = 0; l < 2; l++){
            f = 1;
            for(m = i + 1; m < j; m++){
              if(isecSS(vs[2 * i + k], vs[2 * j + l], vs[2 * m], vs[2 * m + 1]) == false){
                f = 0;
              }
            }
            if(f == 1){
              dis[2 * i + k][2 * j + l] = abs(vs[2 * i + k] - vs[2 * j + l]);
            }
          }
        }
      }
    }
    for(i = 0; i < N - 1; i++){
      for(k = 0; k < 2; k++){
        f = 1;
        for(m = 0; m < i; m++){
          if(isecSS(vs[2 * N - 2], vs[2 * i + k], vs[2 * m], vs[2 * m + 1]) == false){
            f = 0;
          }
        }
        if(f == 1){
          dis[2 * N - 2][2 * i + k] = abs(vs[2 * N - 2] - vs[2 * i + k]);
        }
      }
    }
    for(i = 0; i < N - 1; i++){
      for(k = 0; k < 2; k++){
        f = 1;
        for(m = i + 1; m < N - 1; m++){
          if(isecSS(vs[2 * i + k], vs[2 * N - 1], vs[2 * m], vs[2 * m + 1]) == false){
            f = 0;
          }
        }
        if(f == 1){
          dis[2 * i + k][2 * N - 1] = abs(vs[2 * i + k] - vs[2 * N - 1]);
        }
      }
    }
    f = 1;
    for(m = 0; m < N - 1; m++){
      if(isecSS(vs[2 * N - 2], vs[2 * N - 1], vs[2 * m], vs[2 * m + 1]) == false){
        f = 0;
      }
    }
    if(f == 1){
      dis[2 * N - 2][2 * N - 1] = abs(vs[2 * N - 2] - vs[2 * N - 1]);
    }
    for(k = 0; k < 2 * N; k++){
      for(i = 0; i < 2 * N; i++){
        for(j = 0; j < 2 * N; j++){
          dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
      }
    }
    printf("%.9lf\n", dis[2 * N - 2][2 * N - 1]);
  }
}



Measured memory_bytes: 3460