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

#define DEBUG 1

#define INF (1.0/0.0)
#define EPS 1e-8
#define PI 3.1415926535
#define EQ(x, y) (abs((x)-(y))<EPS)
#define X real()
#define Y imag()

typedef complex<double> Point;
typedef Point Vec;
typedef array<Point, 2> Line;
typedef vector<Point> Poly;

struct Circle {
  Point c;
  double r;
};

enum Geometory {ABC=-2, CW, ON_LINE, CCW, CAB, OUTSIDE, INSIDE, ERROR}; 

namespace std {
  bool operator<(Point a, Point b) {
    if (!EQ(a.X, b.X)) return a.X < b.X;
    if (!EQ(a.Y, b.Y)) return a.Y < b.Y;
    return false;
    //return a.Y < b.Y;
  }

  bool operator>(Point a, Point b) {
    return b<a;
  }

  bool operator<=(Point a, Point b) {
    return !(a>b);
  }
}

double dot(Point a, Point b) {
  return (conj(a)*b).X;
}

double cross(Point a, Point b) {
  return (conj(a)*b).Y;
}

Geometory ccw(Point a, Point b, Point c) {
  b -= a;
  c -= a;
  if (cross(b, c) > EPS) return CCW; // ccw
  if (cross(b, c) < -EPS) return CW; // cw
  if (dot(b, c) < 0) return CAB; // c - a - b
  if (norm(b) < norm(c)) return ABC; // a - b - c
  return ERROR;
}

Point proj(Line l, Point p) {
  Point v = l[1]-l[0];
  double ratio = dot(v, p-l[0]) / norm(v);
  return l[0] + ratio*v;
}

Point refl(Line l, Point p) {
  return p + (proj(l, p) - p) * 2.0;
}

Vec rotate(Vec v, double r) {
  return v*Vec(cos(r), sin(r));
}

bool IsOrthogonal(Line l, Line m) {
  Vec v1 = l[1]-l[0];
  Vec v2 = m[1]-m[0];
  return EQ(dot(v1, v2), 0.0);
}

bool IsParallel(Line l, Line m) {
  Vec v1 = l[1]-l[0];
  Vec v2 = m[1]-m[0];
  return EQ(cross(v1, v2), 0.0);
}

bool IntersectLL(Line l, Line m) {
  if (!EQ(cross(l[1]-l[0], m[1]-m[0]), 0.0)) return true;
  if (EQ(cross(l[1]-l[0], m[0]-l[0]), 0.0)) return true;
  return false;
}

bool IntersectLS(Line l, Line s) {
  Point b = l[0];
  Vec v = l[1]-l[0];
  return cross(v, s[0]-b)*cross(v, s[1]-b) < EPS;
}

bool IntersectSS(Line s, Line t) {
  if (ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) > 0) return false;
  if (ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) > 0) return false;
  return true;
}

bool IntersectLP(Line l, Point p) {
  return EQ(cross(l[1]-p, l[0]-p), 0.0);
}

bool IntersectSP(Line s, Point p) {
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS;
}

double DistL(Line l) {
  return abs(l[0]-l[1]);
}

double DistLP(Line l, Point p) {
  return abs(p - proj(l, p));
}

double DistLL(Line l, Line m) {
  if (!IntersectLL(l, m)) return 0;
  return DistLP(l, m[0]);
}

double DistLS(Line l, Line s) {
  if (IntersectLS(l, s)) return 0;
  return min(DistLP(l, s[0]), DistLP(l, s[1]));
}

double DistSP(Line s, Point p) {
  Point r = proj(s, p);
  if (IntersectSP(s, r)) return abs(r - p);
  return min(abs(s[0]-p), abs(s[1]-p));
}

double DistSS(Line s, Line t) {
  if (IntersectSS(s, t)) return 0;

  double a = min(DistSP(s, t[0]), DistSP(s, t[1]));
  double b = min(DistSP(t, s[0]), DistSP(t, s[1]));
  return min(a, b);
}

Line PerpendBisect(Line seg) {
  Point mid = (seg[0]+seg[1])/2.0;
  return Line{mid, mid+(seg[1]-seg[0])*Vec(0, 1)};
}

Point CrossPointLL(Line l, Line m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0];
  if (abs(A) < EPS) assert(0);
  return m[0] + B / A * (m[1]-m[0]);
}

vector<Point> CrossPointCL(Circle c, Line l) {
  vector<Point> ret;
  double d = DistLP(l, c.c);
  if (d < c.r + EPS) {
    double ratio = (d > c.r) ? 0.0 : sqrt(c.r*c.r - d*d);
    Vec sgn = (l[0]-l[1]) / abs(l[0]-l[1]);
    ret.emplace_back(proj(l, c.c) + ratio*sgn);
    ret.emplace_back(proj(l, c.c) - ratio*sgn);
  }
  return ret;
}

vector<Point> CrossPointCS(Circle c, Line s) {
  vector<Point> ret;
  vector<Point> res = CrossPointCL(c, s);
  if (s[0] > s[1]) swap(s[0], s[1]);
  for (Point p : res) {
    if (s[0] <= p && p <= s[1]) ret.emplace_back(p);
  }
  return ret;
}

vector<Point> CrossPointCC(Circle c1, Circle c2) {
  vector<Point> ret;
  double d = abs(c1.c - c2.c);
  double rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
  double dfr = c1.r*c1.r - rc*rc;

  if (EQ(dfr, 0.0)) dfr = 0.0;
  else if(dfr < 0.0) return ret;

  double rs = sqrt(dfr);
  Vec sgn = (c2.c - c1.c) / d;
  ret.emplace_back(c1.c + sgn*Point(rc, rs));
  if (dfr > 0.0) ret.emplace_back(c1.c + sgn*Point(rc, -rs));
  return ret;
}

// Note that ccw(a, b, c) != CCW when a, b, c are colinear
Poly GrahamScan(vector<Point> ps) {
  int k = 0;
  int n = ps.size();
  Poly ret(n*2);

  sort(ps.begin(), ps.end());
  for (int i=0; i<n; i++) {
    while (k > 1 && ccw(ret[k-2], ret[k-1], ps[i]) != CCW) k--;
    ret[k++] = ps[i];
  }

  int k_ = k;
  for (int i=n-1; i>=0; i--) {
    while (k > k_ && ccw(ret[k-2], ret[k-1], ps[i]) != CCW) k--;
    ret[k++] = ps[i];
  }

  ret.resize(k-1);
  return ret;
}

double CalcArea(Poly ps) {
  double ret = 0.0;
  for (int i=0; i<ps.size(); i++) {
    ret += cross(ps[i], ps[(i+1)%ps.size()]);
  }
  return ret/2.0;
}

bool IsConvex(Poly ps) {
  return GrahamScan(ps).size() == ps.size();
}

Geometory ContainsPoint(Poly poly, Point p) {
  bool in = false;
  int n = poly.size();
  for (int i=0; i<n; i++) {
    Point a = poly[i];
    Point b = poly[(i+1)%n];
    Vec u = a - p;
    Vec v = b - p;

    if (u.Y > v.Y) swap(u, v);

    double cr = cross(u, v);
    if (u.Y <= 0 && 0 < v.Y && cr > EPS) in ^= 1;
    if (IntersectSP({a, b}, p)) return ON_LINE;
  }

  if (in) return INSIDE;
  return OUTSIDE;
}

// Convex* requires the elements of ps to be arranged counter clockwise.
pair<int, int> ConvexDiameterApexes(Poly ps) {
#if DEBUG
  assert (IsConvex(ps));
#endif

  int n = ps.size();
  int is = 0;
  int js = 0;
  for (int i=1; i<n; i++) {
    if (ps[i].Y > ps[is].Y) is = i;
    if (ps[i].Y < ps[js].Y) js = i;
  }

  int maxi, maxj;
  double maxd = norm(ps[is]-ps[js]);
  int i = is;
  int j = js;
  do {
    Vec a = ps[i+1] - ps[i];
    Vec b = ps[j+1] - ps[j];
    if (cross(a, b) > -EPS) j = (j+1)%n;
    else i = (i+1)%n;

    double d = norm(ps[i]-ps[j]);
    if (d > maxd) {
      maxd = d;
      maxi = i;
      maxj = j;
    }
  } while (i != is || j != js);

  return make_pair(maxi, maxj);
}

Line ClosestPair(vector<Point> ps) {
  auto CompareY = [](const Point &a, const Point &b) {
    if (a.Y != b.Y) return a.Y < b.Y;
    return a.X < b.X;
  };

  function<Line(Point*,int)> Rec = [&Rec, &CompareY](Point *ps, int n) {
    if (n <= 1) return Line{Point(0, 0), Point(INF, INF)};
    
    int m = n/2;
    double x = ps[m].X;
    Line a = Rec(ps, m);
    Line b = Rec(ps+m, n-m);
    double mind = DistL(a);
    Line ret = a;
    if (DistL(b) < mind) {
      mind = DistL(b);
      ret = b;
    }

    sort(ps, ps+n, CompareY);
    vector<Point> qs;
    qs.reserve(n);
    for (int i=0; i<n; i++) {
      if (abs(ps[i].X - x) >= mind) continue;

      for (int j=0; j<qs.size(); j++) {
        Point p1 = ps[i];
        Point p2 = qs[qs.size()-1-j];
        if (p1.Y - p2.Y >= mind) break;

        double d = abs(p1-p2);
        if (mind > d) {
          mind = d;
          ret = Line{p1, p2};
        }
      }

      qs.emplace_back(ps[i]);
    }

    return ret;
  };

  int n = ps.size();
  assert (n >= 2);
  sort(ps.begin(), ps.end());
  return Rec(&ps[0], n);
}

// Convex* requires the elements of ps to be arranged counter clockwise.
// <left, right> or <upper, lower>
pair<Poly, Poly> CutConvex(Poly ps, Line l) {
#if DEBUG
  assert (IsConvex(ps));
#endif

  //if (l[0].Y > l[1].Y) swap(l[0], l[1]);
  //else if (EQ(l[0].Y, l[1].Y) && l[0].X > l[1].X) swap(l[0], l[1]);

  Poly left;
  Poly right;
  for (int i=0; i<ps.size(); i++) {
    Point a = ps[i];
    Point b = ps[(i+1)%ps.size()];

    if (ccw(l[0], l[1], a) != CW) left.emplace_back(a);
    else right.emplace_back(a);

    Line m{a, b};
    if (IntersectLS(l, m)) {
      Point p = CrossPointLL(l, m);
      left.emplace_back(p);
      right.emplace_back(p);
    }
  }

  return make_pair(left, right);
}

Circle Circum(Point a, Point b, Point c) {
  Circle ret{{INF, INF}, 0.0};
  Line l{a, b};
  Line m{b, c};
  Line lp = PerpendBisect(l);
  Line mp = PerpendBisect(m);
  if (IsParallel(lp, mp)) return ret;

  ret.c = CrossPointLL(lp, mp);
  ret.r = abs(a-ret.c);
  return ret;
}
int n;
Circle cs[114514];
double mind[400][400];
vector<Point> ps;

typedef pair<Point, int> Event;
vector<Event> es;

int main() {
  while (1) {
    scanf("%d", &n);
    if (n == 0) return 0;

    ps.clear();
    for (int i=0; i<n; i++) {
      int x, y;
      double r;
      scanf("%d%d%lf", &x, &y, &r);
      cs[i] = Circle{Point(x, y), r};
      ps.push_back(cs[i].c);
    }
  
    for (int i=1; i<n; i++) {
      vector<Point> cros = CrossPointCC(cs[i-1], cs[i]);
      assert (cros.size() == 2);
      ps.push_back(cros[0]);
      ps.push_back(cros[1]);
    }
    //sort(ps.begin(), ps.end());
  
    int m = ps.size();
    for (int i=0; i<m; i++) for (int j=0; j<m; j++) mind[i][j] = INF;
    for (int i=0; i<m; i++) {
      mind[i][i] = 0;
      for (int j=i+1; j<m; j++) {
        es.clear();

        //printf("consider %d %d %f %f %f %f\n", i, j, ps[i].X, ps[i].Y, ps[j].X, ps[j].Y);
        for (int k=0; k<n; k++) {
          vector<Point> cros = CrossPointCS(cs[k], Line{ps[i], ps[j]});
          if (cros.empty()) continue;
  
          if (cros.size() == 1) {
            double id = abs(ps[i]-cs[k].c);
            double jd = abs(ps[j]-cs[k].c);
            if (id < min(jd, cs[k].r)) cros.push_back(ps[i]);
            else if (jd < min(id, cs[k].r)) cros.push_back(ps[j]);
            else { 
              Point p = cros[0];
              cros.push_back(p);
            }
          }
  
          if (cros[1] < cros[0]) {
            swap(cros[0], cros[1]);
          }
  
          //printf("%f %f %f %f\n", cros[0].X, cros[0].Y, cros[1].X, cros[1].Y);
          es.push_back(Event(cros[0], -1));
          es.push_back(Event(cros[1], +1));
  
          Vec v1 = ps[i]-cs[k].c;
          Vec v2 = ps[j]-cs[k].c;
          if (EQ(abs(v1), cs[k].r) && EQ(abs(v2), cs[k].r)) {
            double ar = abs(arg(v2/v1)) * cs[k].r;
            double g = min(mind[i][j], ar);
            mind[i][j] = mind[j][i] = g;
          }
        }
  
        sort(es.begin(), es.end());
        int cnt = 0;
        bool fail = false;
        Point lim = Point(-INF, -INF);
        for (int idx=0; idx<es.size(); idx++) {
          Event &e = es[idx];
          Point p = e.first;
          //printf("%d: %f %f\n", idx, p.X, p.Y);
          if (idx == 0 && !EQ(p, min(ps[i], ps[j]))) {
            //printf("%f %f %f %f\n", min(ps[i], ps[j]).X, min(ps[i], ps[j]).Y, p.X, p.Y);
            
            fail = true;
            break;
          }

          cnt += e.second;
          lim = max(lim, p);
          if (cnt > 0 || (cnt == 0 && idx < es.size()-1)) {
            fail = true;
            break;
          }
          //printf("%d %d cnt: %d st: %d\n", i, j, cnt, fail);
        }
        //printf("%f %f\n", lim.X, lim.Y);
        if (!es.empty() && !EQ(lim, max(ps[i], ps[j]))) fail = true;
  
        if (!fail) {
          mind[i][j] = mind[j][i] = abs(ps[i]-ps[j]);
          //printf("connect %d %d %f\n", i, j, mind[i][j]);
        }
      }
    }
  
    for (int k=0; k<m; k++) {
      for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
          mind[i][j] = min(mind[i][j], mind[i][k]+mind[k][j]);
          //printf("mind %d %d %f\n", i, j, mind[i][j]);
        }
      }
    }
  
    //printf("ans: %.10f\n", mind[0][n-1]);
    printf("%.10f\n", mind[0][n-1]);
  }
}

Measured memory_bytes: 7056