#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)
using namespace std;

using ld = long double;
using P = complex<ld>;
using VP = vector<P>;
const ld eps = 1e-8, pi = acos(-1.0);

#define EQ(a,b) (abs((a)-(b))<eps)

ld dot (P a, P b) { return real(conj(a) * b); }
ld cross (P a, P b) { return imag(conj(a) * b); }

struct L{ P a, b; };
struct C { P p; ld r; };

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

bool isis_ss(L s, L t) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
         ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

VP is_cc(C c1, C c2){
  VP res;
  ld d = abs(c1.p - c2.p);
  ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
  ld dfr = c1.r * c1.r - rc * rc;
  if (abs(dfr) < eps) dfr = 0.0;
  else if (dfr < 0.0) return res; // no intersection
  ld rs = sqrt(dfr);
  P diff = (c2.p-c1.p)/d;
  res.push_back(c1.p + diff * P(rc, rs));
  if (dfr != 0.0) res.push_back(c1.p + diff * P(rc, -rs));
  return res;
}
typedef double Weight;
Weight INF = 1000000000;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
  g[dest].push_back((Edge){dest, src, weight});
}

// Dijkstra (Verified: AOJ2005)
void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int main() {
  while (true) {
    int n;
    cin >> n;
    if(!n) break;
    vector<C> vc(n);
    REP(i,n) {
      ld x,y,r;
      cin>>x>>y>>r;
      vc[i] = {P(x,y), r};
    }
    vector<VP> vvp;
    REP(i,n-1) {
      vvp.emplace_back(is_cc(vc[i], vc[i+1]));
    }
    int m=2*n;
    Graph g(m);
    P s = vc.front().p;
    P t = vc.back().p;
    REP(i,2) {
      add_edge(g, 0, i+1, abs(s - vvp.front()[i]));
      add_edge(g, m-1, m-3+i, abs(t - vvp.back()[i]));
    }
    L st = {s, t};
    bool ok = true;
    REP(i,n-1) {
      L crs = {vvp[i][0], vvp[i][1]};
      if (!isis_ss(st, crs)) {
        ok = false;
      }
    }
    if (ok) {
      add_edge(g, 0, m-1, abs(s-t));
    }
    FOR(i,1,n-1) {
      REP(j,2) {
        int revi = n-i-2;
        L sl = {s, vvp[i][j]};
        L tl = {t, vvp[revi][j]};
        bool oks = true;
        bool okt = true;
        REP(k, i) {
          L crss = {vvp[k][0], vvp[k][1]};
          L crst = {vvp[n-k-2][0], vvp[n-k-2][1]};
          if (!isis_ss(sl, crss)) {
            oks = false;
          }
          if (!isis_ss(tl, crst)) {
            okt = false;
          }
        }
        if (oks) {
          add_edge(g, 0, 2*i+j+1, abs(s - vvp[i][j]));
        }
        if (okt) {
          add_edge(g, m-1, 2*revi+j+1, abs(t - vvp[revi][j]));
        }
      }
    }
    REP(i,n-1)REP(j,i) {
      REP(k,2)REP(l,2) {
        L nl = {vvp[i][k], vvp[j][l]};
        bool ok = true;
        FOR(p,j+1,i) {
          L crs = {vvp[p][0], vvp[p][1]};
          if (!isis_ss(nl, crs)) {
            ok = false;
          }
        }
        if (ok) {
          add_edge(g, j*2+l+1, i*2+k+1, abs(nl.a - nl.b));
        }
      }
    }
    Array res(m);
    dijkstra(g, res, 0);
    cout << fixed << setprecision(6) << res[m-1] << endl;
  }
  return 0;
}

Measured memory_bytes: 3360