#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<complex>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<cassert>
using namespace std;

typedef complex<double> P;

#define REP(i,n) for(int i=0;i<(int)n;++i)


const double EPS = 1e-8;
inline double dot(P a, P b) {return real( conj(a)*b);}
inline double cross(P a, P b) {return imag( conj(a)*b);}
inline double sq(double x) {return x * x;}
inline int signum(double x) {return x > EPS ? +1 : x < -EPS ? -1 : 0;} // 未検証

struct C : public P {
  double r;
  C() {}
  C(const P &p,double r):P(p),r(r){}
};

// 2円の交点
vector<P> IntersectionCC(const C& c1, const C& c2) {
  vector<P> ret;
  double d = abs(c1 - c2);
  P diff = (c2 - c1) / d;
  if( c1.r + c2.r < d - EPS ) {                        // 離れていて交点0

  } else if( d < EPS && abs(c1.r - c2.r) < EPS ) {     // 2円が重なる

  } else if( abs( c1.r + c2.r - d ) < EPS ) {          // 外側で1点で接する
      ret.push_back( c1 + diff * c1.r );
  } else if( abs( c1.r - c2.r ) > d + EPS ) {          // 内側に含む。交点0

  } else if( abs( abs( c1.r - c2.r ) - d ) < EPS) {    // 内側で1点で接する
      ret.push_back( c1 + diff * c1.r );
  } else {                                            // 2点で交わる
//     assert( d < c1.r + c2.r );
      double rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
      double rs = sqrt(c1.r*c1.r - rc*rc);

      ret.push_back( c1 + diff * P(rc, -rs) );
      ret.push_back( c1 + diff * P(rc, rs) );
  }
  return ret;
}

bool IsIntersectSP(P a, P b, P c) {
  return (abs(a-c) + abs(c-b) < abs(a-b) + EPS);
}
bool IsIntersectLL(P a,P b,P c,P d){
  return abs(cross(b-a, d-c)) > EPS || // non-parallel
      abs(cross(b-a, c-a)) < EPS;   // same line
}
P IntersectionLL(P a1, P a2, P b1, P b2) {
  P a = a2 - a1; P b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}
double DistanceLP(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}
// ベクトルpをベクトルbに射影したベクトルを計算する
P proj(P p, P b) {
  return b * dot(p,b) / norm(b);
}

// 点pから直線abに引いた垂線の足となる点を計算する
P FootOfLP(P a, P b, P p){
  return a + proj(p-a,b-a);
}


// 直線abと円cの交点をvectorで返す
vector<P> IntersectionLC(P a, P b, C c){
  double dist = DistanceLP(a,b,c);
  vector<P> ret;
  if( abs(dist - c.r) < EPS ) {
      ret.push_back( FootOfLP(a,b,c) );
  } else if( dist < c.r ) {
      P m = FootOfLP(a,b,c);
      P u = (b-a) / abs(b-a);
      double t = sqrt( c.r * c.r - dist * dist );
      ret.push_back( m + t * u );
      ret.push_back( m - t * u );
  }
  return ret;
}


int N;
vector<C> c;
vector<P> p;

bool canSee(P a, P b) {

  {
      P m = (a + b) / 2.0;

      int in = 0;
      for (int j = 0; j < c.size(); j++) {
          double d = abs(c[j] - m);
          if (d < c[j].r - EPS) {
              in++;
          }
          if (d < c[j].r + EPS) {
              in++;
          }
      }
      if (in <= 1) return false;
  }

  REP(i, c.size()) {
      vector<P> cur = IntersectionLC(a, b, c[i]);
      for (int j = 0; j < cur.size(); j++) {
          if (IsIntersectSP(a, b, cur[j])) {
              P m = cur[j];

              int in = 0;
              for (int j = 0; j < c.size(); j++) {
                  double d = abs(c[j] - m);
                  if (d < c[j].r - EPS) {
                      in++;
                  }
                  if (d < c[j].r + EPS) {
                      in++;
                  }
              }
              if (in <= 1) return false;

          }
      }
  }

  return true;
}

int psize;
double dist[512][512];

int main() {
  for (; cin >> N && N; ) {
      c.clear();
      p.clear();
      REP(i,N) {
          int x, y, r; cin >> x >> y >> r;
          c.push_back(C(P(x,y), r));
      }
      p.push_back(c[0]);
      p.push_back(c[N-1]);

      REP(i, N) {
          REP(j, i) if ( abs(i - j) <= 2) {
              double d = abs(c[i] - c[j]);
              if(c[i].r + c[j].r <= d + EPS) {

              } else {
                  vector<P> m = IntersectionCC(c[i], c[j]);
                  for (int i = 0; i < m.size(); i++)
                      p.push_back(m[i]);
              }
          }
      }

      psize = p.size();
      REP(i, psize) {
          REP(j, i) {
              if (canSee(p[i], p[j])) {
                  dist[i][j] = dist[j][i] = abs(p[i] - p[j]);
              } else {
                  dist[i][j] = dist[j][i] = 1001001001;
              }
          }
      }

      REP(k, psize) REP(i, psize) REP(j, psize) {
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }

//       cout << "d" << endl;

//       cout << "---" << endl;
//       REP(k, psize) {
//           if (abs(-dist[0][1] + dist[0][k] + dist[k][1]) < EPS)
//               cout << p[k] << endl;
//       }

      printf("%.8f\n", dist[0][1]);

  }
  return 0;
}

Measured memory_bytes: 1780