#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <queue>
using namespace std;

typedef double D;

const D EPS = 1e-8;
const D INF = 1e9;

int sig(D a, D b) {
  if(a < b - EPS) return -1;
  if(a > b + EPS) return +1;
  return 0;
}

struct P {
  D x,y;
  P() { }
  P(D x_, D y_) : x(x_), y(y_) { }
};

struct L {
  P a,b;
  L() { }
  L(P a_, P b_) : a(a_), b(b_) { }
};

struct C {
  P p; D r;
  C() { }
  C(P p_, D r_) : p(p_), r(r_) { }
};

P operator +(P a, P b) {
  return P(a.x + b.x, a.y + b.y);
}

P operator -(P a, P b) {
  return P(a.x - b.x, a.y - b.y);
}

P operator *(P a, D b) {
  return P(a.x * b, a.y * b);
}

P operator /(P a, D b) {
  return P(a.x / b, a.y / b);
}

ostream& operator <<(ostream &os, const P &p) {
  os << "{ x = " << p.x << ", y = " << p.y << " }";
  return os;
}

ostream& operator <<(ostream &os, const C &c) {
  os << "{ p = " << c.p << ", r = " << c.r << " }";
  return os;
}


D inp(P a, P b) {
  return a.x*b.x + a.y*b.y;
}

D outp(P a, P b) { return a.x*b.y - a.y*b.x; }

D norm(P a) {
  return inp(a,a);
}

D abs(P a) {
  return sqrt(norm(a));
}

P rot90(P a) {
  return P(-a.y, a.x);
}

P vec(P from, P to) { return to - from; }

int ccw(P a, P b, P c) {
  b = vec(a, b); c = vec(a, c);

  // a - b - c が折れ曲がるとき
  if(sig(outp(b, c), 0.0) > 0) return +1; // 反時計回り
  if(sig(outp(b, c), 0.0) < 0) return -1; // 時計回り

  // a - b - c が直線上に並ぶとき
  if(sig(inp(b, c), 0.0) < 0) return +2; // c - a - b
  if(norm(b) < norm(c))   return -2; // a - b - c
  return 0;                          // a - c - b
}

bool iSS(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;
}

// 2点で接していることを確認すること
vector<P> cCC(C a, C b) {
  D d = abs(b.p - a.p);
  D x = (d*d + a.r*a.r - b.r*b.r) / (2*d);
  D y = sqrt(a.r*a.r - x*x);
  P v = (b.p - a.p) / d;
  vector<P> res;
  res.emplace_back(a.p + v*x + rot90(v)*y);
  res.emplace_back(a.p + v*x - rot90(v)*y);
  return res;
}

struct Edge {
  int to; double cost;
  Edge() { }
  Edge(int to_, double cost_) : to(to_), cost(cost_) { }
};

struct State {
  int pos; double cost;
  State() { };
  State(int pos_, double cost_) : pos(pos_), cost(cost_) { }
  bool operator >(const State &rhs) const {
    return cost > rhs.cost;
  }
};

double shortest_path(const vector<vector<Edge>> &G, const int src, const int dst) {
  double d[G.size()];
  fill(d, d + G.size(), INF);
  d[src] = 0.0;
  priority_queue<State, vector<State>, greater<State>> Q;
  Q.emplace(src, 0.0);
  while(!Q.empty()) {
    State s = Q.top(); Q.pop();
    if(s.cost > d[s.pos]) continue;
    for(const Edge &e : G[s.pos]) {
      if(d[e.to] > d[s.pos] + e.cost) {
        d[e.to] = d[s.pos] + e.cost;
        Q.emplace(e.to, d[e.to]);
      }
    }
  }
  return d[dst];
}

int main() {
  while(true) {
    int n; cin >> n;
    if(n == 0) break;
    vector<C> circle(n);
    for(int i = 0; i < n; ++i) {
      cin >> circle[i].p.x >> circle[i].p.y >> circle[i].r;
    }
    vector<vector<P>> cross(n-1);
    for(int i = 0; i < n - 1; ++i) {
      cross[i] = cCC(circle[i], circle[i+1]);
    }
    vector<vector<Edge>> G(2*(n-1)+2);
    G[2*(n-1)].emplace_back(0, abs(circle[0].p - cross[0][0]));
    G[2*(n-1)].emplace_back(1, abs(circle[0].p - cross[0][1]));
    G[2*(n-1)-1].emplace_back(2*(n-1)+1, abs(cross[n-2][0] - circle[n-1].p));
    G[2*(n-1)-2].emplace_back(2*(n-1)+1, abs(cross[n-2][1] - circle[n-1].p));
    for(int i = 0; i < n - 2; ++i) {
      G[2*i].emplace_back(2*i+2, abs(cross[i][0] - cross[i+1][0]));
      G[2*i].emplace_back(2*i+3, abs(cross[i][0] - cross[i+1][1]));
      G[2*i+1].emplace_back(2*i+2, abs(cross[i][1] - cross[i+1][0]));
      G[2*i+1].emplace_back(2*i+3, abs(cross[i][1] - cross[i+1][1]));
    }
    {
      bool ok = true;
      for(int i = 0; i < n - 1; ++i) {
        if(iSS(L(circle[0].p, circle[n-1].p), L(cross[i][0], cross[i][1])) == false) ok = false;
      }
      if(ok) G[2*(n-1)].emplace_back(2*(n-1)+1, abs(circle[0].p - circle[n-1].p));
    }
    {
      for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < 2; ++j) {
          bool ok = true;
          for(int k = 0; k < i; ++k) {
            if(iSS(L(circle[0].p, cross[i][j]), L(cross[k][0], cross[k][1])) == false) ok = false;
          }
          if(ok) {
            G[2*(n-1)].emplace_back(2*i+j, abs(circle[0].p - cross[i][j]));
          }
        }
      }
    }
    {
      for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < 2; ++j) {
          bool ok = true;
          for(int k = i + 1; k < n - 1; ++k) {
            if(iSS(L(circle[n-1].p, cross[i][j]), L(cross[k][0], cross[k][1])) == false) ok = false;
          }
          if(ok) {
            G[2*i+j].emplace_back(2*(n-1)+1, abs(circle[n-1].p - cross[i][j]));
          }
        }
      }
    }
    {
      for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < 2; ++j) {
          for(int i2 = i + 1; i2 < n - 1; ++i2) {
            for(int j2 = 0; j2 < 2; ++j2) {
              bool ok = true;
              for(int k = i + 1; k < i2; ++k) {
                if(iSS(L(cross[i][j], cross[i2][j2]), L(cross[k][0], cross[k][1])) == false) ok = false;
              }
              if(ok) {
                G[2*i+j].emplace_back(2*i2+j2, abs(cross[i][j] - cross[i2][j2]));
              }
            }
          }
        }
      }
    }
    cout.setf(ios::fixed);
    cout.precision(4);
    cout << shortest_path(G, 2*(n-1), 2*(n-1)+1) << endl;
  }
}

Measured memory_bytes: 1412