#include <bits/stdc++.h>
using namespace std;

// conj(x) : complex conjugate,(0,1)->(0,-1)
// abs(x) : dist between(0,0) and x
// norm(x) : abs(x) * abs(x)
// arg(x) : argment,[-PI,PI]
using CP = complex<long double>;
#define X real()
#define Y imag()
const long double PI = acos(-1.0L);
const long double EPS = 1e-10;
// cos a
long double costh(long double a, long double b,
                  long double c) {
  return (b * b + c * c - a * a) / (2.0L * b * c);
}

// dot(a,b) = |a||b|cos x
long double dot(CP a, CP b) { return (conj(a) * b).X; }
// cross(a,b) : area of parallelogram
// sign : a-> b ,counter clockwise? + : -
long double cross(CP a, CP b) { return (conj(a) * b).Y; }
long double corner(CP a, CP b) {
  //[0,PI]
  return acos(dot(a, b) / (abs(a) * abs(b)));
}

CP projection(CP s, CP t, CP p) {
  CP base = t - s;
  long double r = dot(p - s, base) / norm(base);
  return s + base * r;
}

CP reflection(CP s, CP t, CP p) {
  CP tmp = (projection(s, t, p) - p);
  tmp *= 2;
  return p + tmp;
}

CP intersectionLL(CP a, CP b, CP c, CP d) {
  return a + (b - a) * (cross(d - c, c - a) /
                        cross(d - c, b - a));
}

bool on_seg(CP s, CP t, CP p) {
  // if not use end point, dot(s - p, t - p) < 0
  return abs(cross(s - p, t - p)) <= 1e-10 &&
         dot(s - p, t - p) <= 0;
}

// crossing lines? (a,b) and (c,d)
bool iscross(CP a, CP b, CP c, CP d) {
  // parallel
  if(abs(cross(a - b, c - d)) <= 1e-10) {
    return on_seg(a, b, c) || on_seg(a, b, d) ||
           on_seg(c, d, a) || on_seg(c, d, b);
  }
  CP isp = intersectionLL(a, b, c, d);
  return on_seg(a, b, isp) && on_seg(c, d, isp);
}

long double distLP(CP s, CP t, CP p) {
  return abs(cross(t - s, p - s) / abs(t - s));
}

// segmentver.
long double distSP(CP s, CP t, CP p) {
  if(dot(t - s, p - s) < 0) return abs(p - s);
  if(dot(s - t, p - t) < 0) return abs(p - t);
  return distLP(s, t, p);
}

// segment and segment
long double distSS(CP a, CP b, CP c, CP d) {
  long double res = 1e18;
  if(iscross(a, b, c, d)) return 0.0L;
  res = min(res, distSP(a, b, c));
  res = min(res, distSP(a, b, d));
  res = min(res, distSP(c, d, a));
  res = min(res, distSP(c, d, b));
  return res;
}

// counter clockwise
bool is_convex(const vector<CP> &v) {
  int n = v.size();
  for(int i = 0; i < n; ++i)
    if(cross(v[(i + 1) % n] - v[i],
             v[(i + 2) % n] - v[(i + 1) % n]) < -EPS)
      return 0;
  return 1;
}

vector<CP> convex_hull(vector<CP> &ps) {
  auto lmd = [&](const CP &l, const CP &r) {
    if(l.X != r.X) return l.X < r.X;
    return l.Y < r.Y;
  };
  vector<CP> qs;
  int psize = ps.size();
  sort(ps.begin(), ps.end(), lmd);
  int k = 0;
  qs.resize(psize * 2);
  for(int i = 0; i < psize; ++i) {
    while(k > 1 && cross(qs[k - 1] - qs[k - 2],
                         ps[i] - qs[k - 1]) <= 0)
      --k;
    qs[k++] = ps[i];
  }
  for(int i = psize - 2, t = k; i >= 0; --i) {
    while(k > t && cross(qs[k - 1] - qs[k - 2],
                         ps[i] - qs[k - 1]) <= 0)
      --k;
    qs[k++] = ps[i];
  }
  qs.resize(k - 1);
  return qs;
}

long double convex_diameter(vector<CP> &newv) {
  vector<CP> v = convex_hull(newv);
  int n = v.size(), i = 0, j = 0;
  if(n == 2) return abs(v[0] - v[1]);
  for(int k = 0; k < n; ++k) {
    if(v[k].X < v[i].X) i = k;
    if(v[k].X > v[j].X) j = k;
  }
  long double res = 0;
  int si = i, sj = j;
  while(i != sj || j != si) {
    res = max(res, abs(v[i] - v[j]));
    if(cross(v[(i + 1) % n] - v[i], v[(j + 1) % n] - v[j]) <
       0)
      (++i) %= n;
    else
      (++j) %= n;
  }
  return res;
}

vector<CP> convex_cut(const vector<CP> &v, const CP &s,
                      const CP &t) {
  vector<CP> res;
  int n = v.size();
  for(int i = 0; i < n; ++i) {
    CP nows = v[i], nowt = v[(i + 1) % n];
    if(cross(t - s, nows - s) >= -EPS) res.push_back(nows);
    if(cross(t - s, nows - s) * cross(t - s, nowt - s) < 0)
      res.push_back(intersectionLL(s, t, nows, nowt));
  }
  return res;
}

struct Circle {
  CP o;
  long double r;
  Circle(long double _x = 0.0L, long double _y = 0.0L,
         long double _r = 0.0L)
      : o(CP(_x, _y)), r(_r) {}
  Circle(CP _o, long double _r = 0.0) : o(_o), r(_r) {}
};

void intersectionCC(Circle c1, Circle c2, CP &res1,
                    CP &res2) {
  long double d = abs(c1.o - c2.o);
  long double arg = acos(costh(c2.r, c1.r, d));
  res1 = (c2.o - c1.o) * CP(cos(arg), sin(arg));
  res1 *= c1.r / abs(res1);
  res1 += c1.o;
  res2 = reflection(c1.o, c2.o, res1);
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

void intersectionCL(Circle ci, CP s, CP t, CP &res1,
                    CP &res2) {
  res1 = res2 = projection(s, t, ci.o);
  long double r = sqrtl(ci.r * ci.r - norm(res1 - ci.o));
  t -= s;
  t *= r / abs(t);
  res1 += t;
  res2 -= t;
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

void contactCP(Circle ci, CP p, CP &res1, CP &res2) {
  long double d = abs(ci.o - p);
  if(abs(d - ci.r) <= EPS) {
    res1 = res2 = p;
    return;
  }
  else if(d < ci.r) {
    res1 = res2 = CP(-1e18, -1e18);
    return;
  }
  long double arg = asin(ci.r / d);
  res1 = (ci.o - p) * CP(cos(arg), sin(arg));
  res1 *= (d * cos(arg)) / abs(res1);
  res1 += p;
  res2 = reflection(p, ci.o, res1);
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

long double polygonarea(const vector<CP> &v) {
  int n = v.size();
  long double res = 0;
  for(int i = 0; i < n; ++i)
    res +=
        (v[(i - 1 + n) % n].X - v[(i + 1) % n].X) * v[i].Y;
  return res / 2.0L;
}

long long calc_clockwise(CP s, CP t, CP p) {
  t -= s;
  p -= s;
  if(cross(t, p) > EPS) return 1;   // "COUNTER_CLOCKWISE"
  if(cross(t, p) < -EPS) return -1; //"CLOCK_WISE"
  if(dot(t, p) < 0) return 2;       // ONLINE_BACK
  if(norm(t) < norm(p)) return -2;  // ONLINE_FRONT
  return 0;                         // ON_SEGMENT
}

long long n;
vector<vector<long double>> dist;
vector<CP> points;
vector<int> id;
vector<Circle> circles;

long double solve();

int main() {
  cout << fixed << setprecision(10);
  while(1) {
    cin >> n;
    if(n == 0) break;
    circles.resize(n);
    for(int i = 0; i < n; ++i) {
      int x, y;
      cin >> x >> y >> circles[i].r;
      circles[i].o = CP(x, y);
    }
    cout << solve() << endl;
  }
  return 0;
}

long double solve() {
  points.clear();
  dist.clear();
  id.clear();
  points.push_back(circles[0].o);
  id.push_back(0);
  for(int i = 0; i < n - 1; ++i) {
    points.push_back(CP(0, 0));
    points.push_back(CP(0, 0));
    id.push_back(i + 1);
    id.push_back(i + 1);
    intersectionCC(circles[i], circles[i + 1],
                   points[1 + 2 * i], points[2 + 2 * i]);
  }
  points.push_back(circles[n - 1].o);
  id.push_back(n);
  int psize = points.size();
  dist.assign(psize, vector<long double>(psize, 1e18));
  for(int i = 0; i < psize; ++i)
    for(int j = i; j < psize; ++j) {
      bool ch = 1;
      CP nowp = points[i], st = points[i], go = points[j];
      if(i == 0) {
        CP dummy1, dummy2;
        intersectionCL(circles[0], st, go, dummy1, dummy2);
        if(norm(dummy2 - go) < norm(dummy1 - go))
          dummy1 = dummy2;
        st = dummy1;
      }
      if(j == psize - 1) {
        CP dummy1, dummy2;
        intersectionCL(circles[n - 1], st, go, dummy1,
                       dummy2);
        if(norm(dummy2 - st) < norm(dummy1 - st))
          dummy1 = dummy2;
        go = dummy1;
      }
      nowp = st;
      for(int k = max(id[i], 1); k < id[j]; ++k) {
        if(distLP(st, go, circles[k].o) >
               circles[k].r + EPS ||
           abs(nowp - circles[k].o) > circles[k].r + EPS) {
          ch = 0;
          break;
        }
        CP p1(0, 0), p2(0, 0);
        intersectionCL(circles[k], st, go, p1, p2);
        if(norm(p2 - points[i]) < norm(p1 - points[i]))
          swap(p1, p2);
        nowp = p2;
      }
      if(ch) dist[i][j] = abs(points[i] - points[j]);
    }
  for(int k = 0; k < psize; ++k)
    for(int i = 0; i < psize; ++i)
      for(int j = 0; j < psize; ++j)
        dist[i][j] =
            min(dist[i][j], dist[i][k] + dist[k][j]);
  return dist[0][psize - 1];
}



Measured memory_bytes: 4072