#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <numeric>
#include <cmath>
#include <iterator>

using namespace std;

#define pb push_back
#define sz size()
#define fs first
#define sc second

#define rep(i, a) for(int i=0;i<(int)(a);i++)
#define EQ(a, b) (abs((a)-(b)) < EPS)


typedef double D;
const D EPS = 1e-12;
const D INF = 1e+10;
const int MAX_N = 100;
typedef complex<D> P;

namespace std{
  bool operator<(const P &a, const P &b){
    return real(a) == real(b) ? imag(a) < imag(b): real(a) < real(b);
  }
}

P unit(P p){ return p / abs(p);}
pair<P, P> norm(P p){ return make_pair(p*P(0, 1), p*P(0, -1));}

D dot(P x, P y){ return real(conj(x)*y);}
D cross(P x, P y){ return imag(conj(x)*y);}

P rotate(P v, double s){
  return P(real(v)*cos(s) - imag(v) * sin(s), real(v) * sin(s) + imag(v) * cos(s));
}

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(abs(b) < abs(c)) return -2; // a--b--c on line
  return 0;
}

D arg(P a, P b, P c){ return acos(dot(b-a,c-a)/(abs(b-a)*abs(c-a)));}
D arg(D a, D b, D c){ return acos((b*b+c*c-a*a)/(2*b*c));}

typedef pair<P, P> L;
typedef pair<P, D> C;

bool in_cir(C c, P x){ return (abs(x-c.fs) + EPS < c.sc);}
bool on_cir(C c, P x){ return EQ(abs(x - c.fs), c.sc); }

vector<L>adj_line(C c, P p){
  vector<L>res;
  if(in_cir(c,p)) return res;
  if(on_cir(c, p)){
    pair<P, P> n = norm(c.fs-p);
    res.pb(L(n.fs + p, p));
    return res;
  }
  D x = c.sc, z = abs(c.fs-p);
  D y = sqrt(z*z-x*x);
  D s = arg(y, x, z);
  P v = unit(p -c.fs) * c.sc;

  res.pb(L(rotate(v, s) + c.fs, p));
  res.pb(L(rotate(v, -s) + c.fs, p));
  return res;
}

vector<P> cp_cir_to_cir(C a, C b){
  vector<P> v;
  D s = arg(b.sc, abs(b.fs-a.fs),a.sc);
  P x = a.sc * unit(b.fs - a.fs);
  v.pb(a.fs + rotate(x, s));
  v.pb(a.fs + rotate(x, -s));
  return v;    
}

vector<L> common_adj_line(C a, C b){
  vector<L> res;
  if(a.sc + EPS < b.sc) return common_adj_line(b, a);
  if(EQ(real(a.fs), real(b.fs)) && EQ(imag(a.fs), imag(b.fs)) && EQ(a.sc, b.sc)) return res;
  P pos = (b.fs - a.fs) * a.sc/(a.sc + b.sc) + a.fs;
  if(!in_cir(a, pos)) res = adj_line(a, pos);

  if(EQ(a.sc, b.sc)){
    pair<P, P> n = norm(unit(b.fs - a.fs) * a.sc);
    res.pb(L(a.fs+n.fs, b.fs + n.fs));
    res.pb(L(a.fs + n.sc, b.fs + n.sc));
  }else{
    D c = abs(b.fs - a.fs);
    pos = unit(b.fs-a.fs)*( (a.sc * c) / (a.sc - b.sc) ) + a.fs;
    if(!in_cir(a, pos)){
      vector<L>tmp = adj_line(a, pos);
      rep(i, tmp.sz) res.pb(tmp[i]);
    }
  }
  return res;
}

D dis(L a, P x){
  return abs(cross(a.sc-a.fs,x-a.fs))/abs(a.sc-a.fs);
}

int ccws(const P a, const P b, const vector<P> c){
  vector<int>x;
  for(int i=0;i<c.size();i++){
    x.push_back(ccw(a, b, c[i]));
  }
  for(int i=0;i<x.size()-1;i++){
    if(x[i] != x[i+1]) return -10;
  }
  return x[0];
}
  
int main(){
  int N;
  while(cin >> N, N){
    vector<P>c(N);
    vector<D>r(N);
    for(int i=0;i<N;i++){
      D x, y;
      cin >> x >> y >> r[i];
      c[i] = P(x, y);
    }

    vector<P> nodesl(N+1);
    vector<P> nodesr(N+1);
    nodesl[0] = c[0];
    nodesr[0] = c[0];
    nodesl[N] = c[N-1];
    nodesr[N] = c[N-1];

    for(int i=0;i<N-1;i++){
      vector<P> cp = cp_cir_to_cir(C(c[i], r[i]), C(c[i+1], r[i+1]));
      nodesr[i+1] = cp[0];
      nodesl[i+1] = cp[1];
    }

    // for(int i=0;i<N+1;i++){
    //   cout << nodesr[i] << endl;
    //   cout << nodesl[i] << endl;
    // }
    double G[2*(MAX_N+1)][2*(MAX_N+1)];
    for(int i=0;i<2*(MAX_N+1);i++){
      for(int j=0;j<2*(MAX_N+1);j++){
	G[i][j] = INF;
      }
    }
    for(int i=0;i<N;i++){
      // nodesl[i] - nodesl[i+1]
      G[i][i+1] = abs(nodesl[i] - nodesl[i+1]);
      // nodesl[i] - nodesr[i+1]
      G[i][i+2+N] = abs(nodesl[i] - nodesr[i+1]);
      // nodesr[i] - nodesr[i+1]
      G[i+N+1][i+2+N] = abs(nodesr[i] - nodesr[i+1]);
      // nodesr[i] - nodesl[i+1]
      G[i+N+1][i+1] = abs(nodesr[i] - nodesl[i+1]);
    }
    for(int i=0;i<N+1;i++){
      for(int j=i+2;j<N+1;j++){
	vector<P> nl(nodesl.begin() + i+1, nodesl.begin() + j);
	vector<P> nr(nodesr.begin() + i+1, nodesr.begin() + j);
	int idx1[4] = {i, i, i+N+1, i+N+1};
	int idx2[4] = {j, j+N+1, j+N+1, j};
	P nis[4] = {nodesl[i], nodesl[i], nodesr[i], nodesr[i]};
	P njs[4] = {nodesl[j], nodesr[j], nodesr[j], nodesl[j]};
	for(int k=0;k<4;k++){
	  P ni = nis[k];
	  P nj = njs[k];
	  int l = ccws(ni, nj, nl);
	  int r = ccws(ni, nj, nr);
	  if(l != -10 && r != -10 && l != r){
	    G[idx1[k]][idx2[k]] = abs(ni - nj);
	    // cout << idx1[k] << " " << idx2[k] << " " << abs(ni - nj) << endl;
	  }
	}
      }
    }

    const int V = 2*(N+1);
    // for(int i=0;i<V;i++){
    //   for(int j=0;j<V;j++){
    // 	if(G[i][j] == INF){
    // 	  printf("%3.2lf ", -1.0);
    // 	}else{
    // 	  printf("%3.2lf ", G[i][j]);
    // 	}
    //   }
    //   printf("\n");
    // }    
    for(int k=0;k<V;k++){
      for(int i=0;i<V;i++){
	for(int j=0;j<V;j++){
	  G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
	}
      }
    }
    // printf("\n");
    // for(int i=0;i<V;i++){
    //   for(int j=0;j<V;j++){
    // 	if(G[i][j] == INF){
    // 	  printf("%3.2lf ", -1.0);
    // 	}else{
    // 	  printf("%3.2lf ", G[i][j]);
    // 	}
    //   }
    //   printf("\n");
    // }        
    // cout << G[0][N] << " " <<  G[0][V-1] << " " <<  G[N+1][N] << " " <<  G[N+1][V-1] << endl;
    printf("%.10lf\n", min({G[0][N], G[0][V-1], G[N+1][N], G[N+1][V-1]}));
  }
  return 0;
}



Measured memory_bytes: 3996