#include <bits/stdc++.h>
using namespace std;
using ll = long long;
double eps = 0.0000001;
using p2 = complex<double>;
// x: real
// y: img

double det(p2 v1, p2 v2) {
  return v1.real() * v2.imag() - v1.imag() * v2.real();
}
double dot(p2 v1, p2 v2) {
  return v1.real() * v2.real() + v1.imag() * v2.imag();
}
bool same(double x, double y) { return fabs(x - y) < eps; }
double dist2(p2 l1, p2 l2) { return dot(l1 - l2, l1 - l2); }
double dist(p2 l1, p2 l2) { return sqrt(dist2(l1, l2)); }

auto p2comp = [](const p2 &l, const p2 &r) {
  if (fabs(l.real() - r.real()) > eps) {
    return l.real() < r.real();
  }
  return l.imag() < r.imag();
};
struct Line {
  p2 st, ed;
  Line(p2 st, p2 ed) : st(st), ed(ed) {}
  Line(double x1, double y1, double x2, double y2)
      : st(p2(x1, y1)), ed(p2(x2, y2)) {}
  Line(p2 st, double x, double y) : st(st), ed(p2(x, y)) {}
  Line(double x, double y, p2 ed) : st(p2(x, y)), ed(ed) {}
  double dist() { return sqrt(dist2(st, ed)); }
  double isPalla(Line l) { return fabs(det(ed - st, l.ed - l.st)) < eps; }
  double x() { return ed.real() - st.real(); }
  double y() { return ed.imag() - st.imag(); }
};

pair<double, double> interP(Line l1, Line l2) {
  double a = l1.x();
  double b = -l2.x();
  double c = l1.y();
  double d = -l2.y();
  double inv = 1. / (a * d - c * b);
  double e1 = -l1.st.real() + l2.st.real();
  double e2 = -l1.st.imag() + l2.st.imag();
  return make_pair((d * e1 - b * e2) * inv, (-c * e1 + a * e2) * inv);
}

bool intersec(Line l1, Line l2) {
  if (l1.isPalla(l2))
    return false;
  auto r = interP(l1, l2);
  return eps < r.first && r.first < 1. - eps && eps < r.second &&
         r.second < 1. - eps;
}

struct Circle {
  p2 p;
  double r;
  Circle(p2 p, double r) : p(p), r(r) {}
  bool include(p2 l) { return dist2(p, r) < r * r + eps; }

  vector<p2> intersec(Circle c) {
    p2 diff = c.p - p;
    double dist = dot(diff, diff);
    double a = (dist + r * r - c.r * c.r) / 2.;
    double D = dist * r * r - a * a;
    if (D < eps)
      return vector<p2>();
    double Dsqrt = sqrt(D);
    vector<p2> ps;
    ps.emplace_back((a * diff.real() + diff.imag() * Dsqrt) / dist + p.real(),
                    (a * diff.imag() - diff.real() * Dsqrt) / dist + p.imag());
    ps.emplace_back((a * diff.real() - diff.imag() * Dsqrt) / dist + p.real(),
                    (a * diff.imag() + diff.real() * Dsqrt) / dist + p.imag());
    return ps;
  }
};

struct L {
  p2 p;
  int i;
};

struct N {
  int i;
  double d;
};
bool operator<(const N &l, const N &r) { return l.d < r.d; }

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0)
      break;
    vector<Circle> v;
    for (int i = 0; i < n; i++) {
      double x, y, r;
      cin >> x >> y >> r;
      v.push_back(Circle(p2(x, y), r));
    }
    vector<L> inter;
    inter.push_back(L{p2(v[0].p), -1});
    vector<Line> ls;
    for (int i = 0; i < n - 1; i++) {
      auto ps = v[i].intersec(v[i + 1]);
      for (auto &p : ps) {
        inter.push_back(L{p, i});
      }
      ls.push_back(Line(ps[0], ps[1]));
    }
    inter.push_back(L{p2(v[n - 1].p), n - 1});
    int goal = inter.size() - 1;

    // st: 0, ed: goal
    multiset<N> q;
    vector<bool> used(inter.size());
    q.insert(N{0, 0.});
    while (q.size() > 0) {
      N now = *q.begin();
      q.erase(q.begin());
      if (used[now.i])
        continue;
      used[now.i] = true;
      if (now.i == goal) {
        printf("%.9lf\n", now.d);
        break;
      }
      for (int j = 0; j < inter.size(); j++) {
        if (now.i == j)
          continue;
        if (used[j])
          continue;
        if (abs(inter[now.i].i - inter[j].i) <= 1) {
          q.insert(N{j, now.d + dist(inter[now.i].p, inter[j].p)});
        } else {
          bool ok = true;

          int ii = min(inter[now.i].i, inter[j].i);
          int jj = max(inter[now.i].i, inter[j].i);

          Line l(inter[now.i].p, inter[j].p);
          for (int k = ii + 1; k < jj; k++) {
            if (!intersec(ls[k], l)) {
              ok = false;
              break;
            }
          }

          if (ok) {
            q.insert(N{j, now.d + dist(inter[now.i].p, inter[j].p)});
          }
        }
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3244