#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <complex>
#include <iomanip>
#include <queue>

using namespace std;

typedef long double R;
typedef complex<R> P;
typedef pair<P,P> L;
typedef pair<P,R> C;
typedef vector<P> Poly;

#define x real()
#define y imag()

const R EPS = 1e-9;
const int INF = 1<<29;

inline bool near(const P& p,const P& q){ return abs(p-q)<EPS;}

R dot(const P& p,const P& q){ return p.x*q.x+p.y*q.y;}
R det(const P& p,const P& q){ return p.x*q.y-p.y*q.x;}

enum LPposit{
  P_CD = -2, //counter direction
  P_CW = -1, //clock wise
  P_OS = 0, //on segment
  P_CCW = 1, //counter clock wise
  P_D = 2 //direction
};

inline R ccw_b(const P& p,const P& q,const P& r){  return det(q-p,r-p);}

LPposit ccw(const P& p, const P& q, const P& r){
  R c = ccw_b(p,q,r);
  if(c<-EPS) return P_CW;
  if(c>EPS) return P_CCW;
  if(dot(q-p,r-p)<-EPS) return P_CD;
  if(dot(p-q,r-q)<-EPS) return P_D;
  return P_OS;
}

inline R Sabs(const L& l){ return abs(l.first-l.second);}
inline R LPdist(const L& l,const P& p){ return abs(ccw_b(l.first,l.second,p))/Sabs(l);}

inline R SPdist(L l,P p){
  R a = abs(l.first-p);
  R b = abs(l.second-p);
  R c = Sabs(l);
  if(b*b+c*c>a*a && a*a+c*c>b*b) return LPdist(l,p);
  return min(a,b);
}

bool crossS(const L& p,const L& q){
  return
    ccw(p.first,p.second,q.first)*ccw(p.first,p.second,q.second)<=0 &&
    ccw(q.first,q.second,p.first)*ccw(q.first,q.second,p.second)<=0;
}

P intersect(const L& p,const L& q){
  P vp = p.second-p.first;
  P vq = q.second-q.first;
  P c(det(vp,p.first), det(vq,q.first));
  return P(det(c, P(vp.x, vq.x)), det(c, P(vp.y, vq.y))) / det(vp, vq);
}

R area(const Poly& p){
  R ret = 0;
  int n = p.size();
  for(int i=0;i<n;++i) ret+=det(p[i],p[(i+1)%n]);
  return abs(ret)/2;
}

/* ?????¨??´???????????? */
vector<P> CLintersect(const L& l,const C& c){
  vector<P> ret;
  R di = LPdist(l,c.first);
  R r = c.second;
  if(di+EPS > r) return ret;
  P v = l.second-l.first;
  v/=abs(v);
  P rv = v*P(0,1);
  rv*=di;
  if(LPdist(l,c.first+rv) > di+EPS) rv=-rv;
  v*=sqrt(r*r-di*di);
  ret.push_back(c.first+rv-v);
  ret.push_back(c.first+rv+v);
  return ret;
}

vector<P> CSintersect(const L& l,const C& c){
  vector<P> u = CLintersect(l,c);
  vector<P> ret;
  for(int i=0;i<u.size();++i){
    if(l.first.x <= u[i].x && u[i].x<=l.second.x &&
       l.first.y <= u[i].y && u[i].y<=l.second.y)
      ret.push_back(u[i]);
  }
  return ret;
}

vector<P> CCintersect(C c,C d){
  vector<P> ret;
  const R dist = abs(c.first-d.first);
  const R cr = c.second;
  const R dr = d.second;

  if(dist > cr+dr) return ret;
  if(dist < abs(cr-dr)) return ret;

  const R s = (cr+dr+dist)/2;
  const R area = sqrt(s*(s-cr)*(s-dr)*(s-dist));
  const R h = 2*area/dist;

  P v = d.first - c.first; v/=abs(v);
  const P m = c.first+sqrt(cr*cr-h*h)*v;
  const P n = v*P(0,1);

  ret.push_back(m+n*h);
  ret.push_back(m-n*h);
  return ret;
}

/* ?????? */
namespace std{
  bool operator < (const P& a,const P& b){
    return a.x!=b.x?a.x<b.x : a.y<b.y;
  }
}
Poly convexHull(vector<P> ps){
  int n = ps.size();
  sort(ps.begin(),ps.end());
  Poly ret(2*n);
  int m=0;
  for(int i=0;i<n;++i){
    while(m>=2 && ccw(ret[m-2],ret[m-1],ps[i])<0) --m;
    ret[m++] = ps[i];
  }
  int t = m;
  for(int i=n-2;i>=0;--i){
    while(m>=t && ccw(ret[m-2], ret[m-1], ps[i])<0) --m;
    ret[m++] = ps[i];
  }

  ret.resize(m-1);
  return ret;
}

int n;
vector<C> circ;
vector<P> ps;
double G[250][250];

double len(L l){
  return abs(l.first-l.second);
}

bool pass(int i,int j,const L& l){
  for(int k=i;k<=j;++k){
    L tmp = L(ps[2*k],ps[2*k+1]);
    if(!crossS(l,tmp)) return false;
  }
  return true;
}

inline double min(double a,double b){
  if(a>b) return b;
  return a;
}

double ans[250];
bool used[250];
void dijkstra(int s){
  int m = n*2;
  for(int i=0;i<250;++i) ans[i]=INF,used[i]=false;
  ans[s] = 0;
  while(true){
    double minw = INF;
    int id = -1;
    for(int i=0;i<m;++i){
      if(minw > ans[i] && !used[i]){
	minw = ans[i];
	id = i;
      }
    }
    if(id==-1) break;
    used[id] = true;
    for(int i=0;i<m;++i)
      ans[i] = min(ans[i],minw + G[id][i]);
  }
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<250;++i)
      for(int j=0;j<250;++j)
	G[i][j] = INF;
    for(int i=0;i<250;++i) G[i][i] = 0;
    circ.clear();
    ps.clear();

    for(int i=0;i<n;++i){
      double p,q,r;
      cin >> p >> q >> r;
      circ.push_back(C(P(p,q),r));
    }
    for(int i=0;i+1<n;++i){
      vector<P> u = CCintersect(circ[i],circ[i+1]);
      ps.push_back(u[0]);
      ps.push_back(u[1]);
    }
    //ps[i] : circ[i],circ[i+1]???2??????
    for(int i=0;i<n-1;++i){
      for(int j=i+1;j<n-1;++j){
	if(pass(i,j,L(ps[2*i],ps[2*j])))
	  G[2*i][2*j] = G[2*j][2*i] = len(L(ps[2*i],ps[2*j]));
	if(pass(i,j,L(ps[2*i],ps[2*j+1])))
	  G[2*i][2*j+1] = G[2*j+1][2*i] = len(L(ps[2*i],ps[2*j+1]));
	if(pass(i,j,L(ps[2*i+1],ps[2*j])))
	  G[2*i+1][2*j] = G[2*j][2*i+1] = len(L(ps[2*i+1],ps[2*j]));
	if(pass(i,j,L(ps[2*i+1],ps[2*j+1])))
	  G[2*i+1][2*j+1] = G[2*j+1][2*i+1] = len(L(ps[2*i+1],ps[2*j+1]));
      }
    }

    /*
    for(int i=0;i<.2*n-3;i+=2)
      G[i][i+1] = G[i+1][i] = abs(ps[2*i+1]-ps[2*i]);
    */      
    //node 2*n-2 : start node
    //node 2*n-1 : end node
    for(int i=0;i<n-1;++i){
      if(pass(0,i,L(circ[0].first,ps[2*i])))
	G[2*n-2][2*i] = G[2*i][2*n-2] = abs(ps[2*i]-circ[0].first);
      if(pass(0,i,L(circ[0].first,ps[2*i+1])))
	G[2*n-2][2*i+1] = G[2*i+1][2*n-2] = abs(ps[2*i+1]-circ[0].first);
      if(pass(i,n-2,L(ps[2*i],circ[n-1].first)))
	G[2*i][2*n-1] = G[2*n-1][2*i] = abs(circ[n-1].first-ps[2*i]);
      if(pass(i,n-2,L(ps[2*i+1],circ[n-1].first)))
	G[2*i+1][2*n-1] = G[2*n-1][2*i+1] = abs(circ[n-1].first-ps[2*i+1]);
    }
    if(pass(0,n-2,L(circ[0].first,circ[n-1].first)))
      G[2*n-2][2*n-1] = G[2*n-1][2*n-2] = abs(circ[n-1].first-circ[0].first);

    /*
    if(n==3){
      for(int i=0;i<2*n;++i)
	for(int j=i+1;j<2*n;++j)
	  if(G[i][j]!=INF) cout << i << ":" << j << " " << G[i][j] << endl;
    }
    */
    dijkstra(2*n-2);
    cout << setprecision(10) << ans[2*n-1] << endl;
  }
  return 0;
}

Measured memory_bytes: 1836