#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long double ldb;
typedef complex<ldb> P;

ldb eps = 1e-8;
// 誤差を考慮した比較 sig(a-b) のように使う
// ret<0 なら a<b, ret>0 なら a>b, ret=0 なら a=b
int sig(ldb a) {return (a<-eps)?-1:(a>eps)?1:0;}
// 誤差を考慮した比較
bool eq(ldb a,ldb b){return abs(a-b)<eps;}

// 内積
ldb dot(P a, P b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}
// 外積
ldb cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

// 円
struct C {
  P p;   //中心
  ldb r; //半径
  C(){}
  C(P p,ldb r):p(p),r(r){}
};
// 直線,線分 (半直線は未確認だけど線分で無限に長いものを作れば良さそう)
struct L {
  P a,b;
  L(P a,P b):a(a),b(b){}
  ldb len(){return abs(a-b);}
};

// iP = intersection Point
// 円の交点 
vector<P> iP(C a,C b) {
  vector<P> res;
  double d = abs(a.p-b.p);
  int ret = sig(d-(a.r+b.r));
  if( ret > 0 ) {
  } else if( eq(d,0) ) {
    return vector<P>(3);
  } else if( ret <= 0 ) {
    double th = acos((d*d+a.r*a.r-b.r*b.r)/(2*d*a.r)); ;
    res.push_back(a.p+polar( a.r, arg(b.p-a.p)+th ));
    if( ret != 0 )res.push_back(a.p+polar( a.r, arg(b.p-a.p)-th ));
  }
  return res;
}

// 線分の交点
P iP(L a,L b) {
  P c = b.b-b.a;
  ldb d1 = abs(cross(c, a.a-b.a));
  ldb d2 = abs(cross(c, a.b-b.a));
  ldb t = d1 / (d1 + d2);
  return a.a + (a.b-a.a) * t;
}

// 線分の交差判定
bool iI(L a,L b) {
  return ( cross(a.b-a.a, b.a-a.a) * cross(a.b-a.a, b.b-a.a) < eps ) &&
    ( cross(b.b-b.a, a.a-b.a) * cross(b.b-b.a, a.b-b.a) < eps );
}
int main(void)
{
  int n;
  C c[111];
  vector<P> v[111];
  vector<int> vn[111];
  ldb dp[111][2];
  for(;;) {
    int sz = 0;
    scanf("%d",&n); if(n==0)break;
    for(int i = 0; i <= n; i++) {
      v[i].clear();
      vn[i].clear();
    }
    for(int i = 0; i <= n; i++) {
      dp[i][0] = dp[i][1] = 1ll<<45;
    }
    dp[0][0] = 0;
    for(int i = 0; i < n; i++) {
      int x,y,r;
      scanf("%d%d%d",&x,&y,&r);
      c[i] = C(P(x,y),r);
      if( i == 0  ) {
        v[i].push_back(P(x,y));
        vn[i].push_back(sz++);
      } else if( i == n-1 ) {
        v[i] = iP(c[i],c[i-1]);
        vn[i].push_back(sz++);
        v[i+1].push_back(P(x,y));
        vn[i+1].push_back(sz++);
      } else {
        v[i] = iP(c[i],c[i-1]);
        vn[i].push_back(sz++);
        vn[i].push_back(sz++);
      }
    }
    /*
    for(int i = 0; i <= n; i++) {
      for(int j = 0; j < int(v[i].size()); j++) {
        cout << v[i][j] << " ";
      }
      cout << endl;
    }
    */
    for(int i = 0; i <= n; i++) {
      for(int j = 0; j < int(v[i].size()); j++) {
        
        for(int ii = i+1; ii <= n; ii++) {
          for(int jj = 0; jj < int(v[ii].size()); jj++) {

            bool ok = true;
            for(int k = i+1; k <= ii && ok; k++) {
              if( v[k].size()>1 && !iI(L(v[i][j],v[ii][jj]),L(v[k][0],v[k][1])) ) {
                //printf("%d %d->%d %d p %d\n",i,j,ii,jj,k);
                ok = false;
              }
            }
            if( ok ) {
              dp[ii][jj] = min(dp[ii][jj],dp[i][j]+L(v[i][j],v[ii][jj]).len());
              //printf("%d %d %Lf\n",ii,jj,dp[ii][jj]);
              //g[vn[i][j]].push_back(edge(vn[ii][jj],0));
              //g[vn[ii][jj]].push_back(edge(vn[i][j],0));
            }
            
          }
        }
        
      }
    }
    printf("%Lf\n",dp[n][0]);
  }
  return 0;
}

Measured memory_bytes: 1284