#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

using R = long double;
constexpr R pi = acos((R)-1), eps = 1e-10;

int sgn(R a) { return (a > eps) - (a < -eps); }
int sgn(R a, R b) { return sgn(a - b); }
using P = complex<R>;
istream& operator>>(istream& i, P& p) { R x, y; i >> x >> y; p = P(x, y); return i; }
ostream& operator<<(ostream& o, P p) { return o << fixed << setprecision(15) << real(p) << ' ' << imag(p); }
bool cmp(P p, P q) { return 2 * sgn(real(p), real(q)) + sgn(imag(p), imag(q)) < 0; }
bool eql(P p, P q) { return !cmp(p, q) and !cmp(q, p); }
R dot(P p, P q) { return real(conj(p) * q); }
R crs(P p, P q) { return imag(conj(p) * q); }
// -2: back, -1: cw, 0: on, 1: ccw, 2: front
int ccw(P p, P q) {
  int s = sgn(crs(p, q));
  if (s) return s;
  if (dot(p, q) < 0) return -2;
  if (dot(p, q - p) > 0) return 2;
  return 0;
}
int ccw(P o, P p, P q) { return ccw(p - o, q - o); }
struct L {
  P s, t;
  P vec() const { return t - s; }
  R abs() const { return std::abs(vec()); }
  R arg() const { return std::arg(vec()); }
};
int ccw(L s, P p) { return ccw(s.s, s.t, p); }

P proj(P p, L l) {
  P e = l.vec() / l.abs();
  return l.s + dot(p - l.s, e) * e;
}
P refl(P p, L l) { return (R)2 * proj(p, l) - p; }
R distPP(P p, P q) { return abs(q - p); }
R distPL(P p, L l) { return distPP(p, proj(p, l)); }
R distPS(P p, L s) {
  P q = proj(p, s);
  if (!ccw(s, q)) return distPP(p, q);
  return min(distPP(p, s.s), distPP(p, s.t));
}
R distLL(L l, L m) {
  if (sgn(crs(l.vec(), m.vec()))) return 0;
  return distPL(l.s, m);
}
R distLS(L l, L s) {
  if (ccw(l, s.s) * ccw(l, s.t) != 1) return 0;
  return min(distPL(s.s, l), distPL(s.t, l));
}
R distSS(L s, L t) {
  if (ccw(s, t.s) * ccw(s, t.t) <= 0 and ccw(t, s.s) * ccw(t, s.t) <= 0) return 0;
  return min({distPS(s.s, t), distPS(s.t, t), distPS(t.s, s), distPS(t.t, s)});
}
P intxn(L l, L m) {
  assert(sgn(crs(l.vec(), m.vec())));
  return l.s + crs(m.s - l.s, m.vec()) / crs(l.vec(), m.vec()) * l.vec();
}

struct C { P o; R r; };
V<P> intxnCL(C c, L l) {
  int s = sgn(distPL(c.o, l), c.r);
  if (s > 0) return {};
  P p = proj(c.o, l);
  if (!s) return {p};
  P q = sqrt(c.r * c.r - norm(p - c.o)) * l.vec() / l.abs();
  return {p - q, p + q};
}
V<P> intxnCC(C c, C d) {
  R a = distPP(c.o, d.o);
  if (!sgn(a)) {
    assert(sgn(c.r, d.r));
    return {};
  }
  P p = polar(c.r / a, acos((a * a + c.r * c.r - d.r * d.r) / (2 * a * c.r)));
  return {c.o + conj(p) * (d.o - c.o), c.o + p * (d.o - c.o)};
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  while (true) {
    int n; cin >> n;
    if (!n) break;
    V<C> cs(n);
    for (auto&& c : cs) {
      cin >> c.o >> c.r;
    }
    VV<R> d(2 * n, V<R>(2 * n, 1e10));
    for (int i = 0; i < 2 * n; ++i) d[i][i] = 0;
    V<P> ps(2 * n);
    for (int i = 0; i < n - 1; ++i) {
      auto v = intxnCC(cs[i], cs[i + 1]);
      ps[2 * i] = v[0], ps[2 * i + 1] = v[1];
    }
    ps[2 * n - 2] = cs[0].o, ps[2 * n - 1] = cs.back().o;
    auto add = [&](int i, int j, int l, int r) -> void {
      for (int k = l; k < r; ++k) {
        if (ccw(ps[i], ps[j], ps[2 * k]) == 1) return;
        if (ccw(ps[i], ps[j], ps[2 * k + 1]) == -1) return;
      }
      d[i][j] = min(d[i][j], distPP(ps[i], ps[j]));
    };
    add(2 * n - 2, 2 * n - 1, 0, n - 1);
    for (int i = 0; i < n - 1; ++i) {
      add(2 * n - 2, 2 * i, 0, i);
      add(2 * n - 2, 2 * i + 1, 0, i);
      add(2 * i, 2 * n - 1, i + 1, n - 1);
      add(2 * i + 1, 2 * n - 1, i + 1, n - 1);
      for (int j = i + 1; j < n - 1; ++j) {
        add(2 * i, 2 * j, i + 1, j);
        add(2 * i, 2 * j + 1, i + 1, j);
        add(2 * i + 1, 2 * j, i + 1, j);
        add(2 * i + 1, 2 * j + 1, i + 1, j);
      }
    }
    for (int k = 0; k < 2 * n; ++k) for (int i = 0; i < 2 * n; ++i) for (int j = 0; j < 2 * n; ++j) {
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }
    cout << fixed << setprecision(15) << d[2 * n - 2][2 * n - 1] << '\n';
  }
}


Measured memory_bytes: 4080