#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-7;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

#include <complex>

typedef complex<double> Point;
typedef vector<Point> Polygon;

static const double INF = 1e+10;

#define CURR(P, i) (P[i])
#define NEXT(P, i) (P[(i + 1) % P.size()])

struct Line : public vector<Point> {
  Line() {;}
  Line(Point a, Point b) { push_back(a); push_back(b); }
};

struct Circle {
  Point p;
  double r;
  Circle() {;}
  Circle(Point p, double r) : p(p), r(r) {;}
};

namespace std {
  bool operator<(const Point &lhs, const Point &rhs) {
    return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real();
  }
}

inline double cross(const Point &a, const Point &b) {
  return imag(conj(a) * b);
}

inline double dot(const Point &a, const Point &b) {
  return real(conj(a) * b);
}


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

inline Point projection(const Line &l, const Point &p) {
  double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
  return l[0] + t * (l[0] - l[1]);
}

inline vector<Point> crosspointLC(const Line &l, const Circle &c) {
  vector<Point> ret;
  Point center = projection(l, c.p);
  double d = abs(center - c.p);
  double t = sqrt(c.r * c.r - d * d);
  if (isnan(t)) { return ret; }
  Point vect = (l[1] - l[0]);
  vect *= t / abs(vect);
  ret.push_back(center - vect);
  if (t > EPS) {
    ret.push_back(center + vect);
  }
  return ret;
}

inline vector<Point> crosspointSC(const Line &s, const Circle &c) {
  vector<Point> ret;
  vector<Point> nret = crosspointLC(s, c);
  for (int i = 0; i < (int)nret.size(); i++) {
    if (intersectSP(s, nret[i])) { ret.push_back(nret[i]); }
  }
  return ret;
}

inline vector<Point> crosspointCC(const Circle &c1, const Circle &c2) {
  vector<Point> ret;
  double d = abs(c1.p - c2.p);
  if (max(c1.r, c2.r) - min(c1.r, c2.r) - d> -EPS) { return ret; }
  double x = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
  Point start = c1.p + (c2.p - c1.p) / d * x;
  Point vect = (c1.p - c2.p) * Point(0.0, 1.0);
  return crosspointLC(Line(start, start + vect), c1);
}


typedef double Weight;
struct Edge {
  int src;
  int dest;
  Weight weight;
  Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const Edge &rhs) const {
    if (weight != rhs.weight) { return weight > rhs.weight; }
    if (src != rhs.src) { return src < rhs.src; }
    return dest < rhs.dest;
  }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  for (int y = 0; y < (int)matrix.size(); y++) {
    for (int x = 0; x < (int)matrix[y].size(); x++) {
      printf("%.8f ", matrix[y][x]);
    }
    puts("");
  }
}


Weight Dijkstra(const Graph &g, int s, int t) {
  const int n = g.size();
  vector<bool> visit(n, false);
  Array dist(n, 2000000000LL);
  priority_queue<Edge> que;
  que.push(Edge(s, s, 0));
  Weight ans = -1;
  dist[s] = 0;
  while (!que.empty()) {
    Edge edge = que.top();
    que.pop();
    int from = edge.dest;
    if (visit[from]) { continue; }
    visit[from] = true;
    if (from == t) {
      ans = edge.weight;
      break;
    }
    for (int i = 0; i < (int)g[from].size(); i++) {
      int to = g[from][i].dest;
      Weight ncost = edge.weight + g[from][i].weight;
      if (visit[to] || ncost >= dist[to] - EPS) { continue; }
      dist[to] = ncost;
      que.push(Edge(from, to, ncost));
    }
  }
  return ans;
}

int n, m;
vector<Circle> cs;
vector<Point> ps;
vector<int> indexes;

int main(int argc, char *argv[]) {
  while (scanf("%d", &n), n) {
    m = 0;
    cs.clear();
    ps.clear();
    indexes.clear();
    REP(i, n) {
      double x, y, r;
      scanf("%lf %lf %lf", &x, &y, &r);
      cs.push_back(Circle(Point(x, y), r));
    }
    ps.push_back(cs[0].p);
    indexes.push_back(0);
    ps.push_back(cs[n - 1].p);
    indexes.push_back(n - 1);
    REP(i, n - 1) {
      vector<Point> nret = crosspointCC(cs[i], cs[i + 1]);
      FORIT(it, nret) {
        ps.push_back(*it);
        indexes.push_back(i);
      }
    }
    m = ps.size();
    Graph g(m);
    REP(j, m) {
      REP(i, j) {
        Line l(ps[i], ps[j]);
        double d = abs(ps[i] - ps[j]);
        int cnt = 0;
        vector<pair<double, int> > events;
        events.push_back(make_pair(EPS, 2));
        events.push_back(make_pair(d - EPS, 0));
        int lower = max(0, min(indexes[i], indexes[j]) - 0);
        int upper = min(n, max(indexes[i], indexes[j]) + 1);
        FOR(k, lower, upper) {
          vector<Point> nret = crosspointSC(l, cs[k]);
          if (nret.size() == 0) {
            continue;
          } else if (nret.size() == 1) {
            double d1 = abs(ps[i] - nret[0]);
            if (abs(ps[i] - cs[k].p) - cs[k].r <= EPS) {
              cnt++;
              events.push_back(make_pair(d1 + EPS, -1));
            } else {
              events.push_back(make_pair(d1 - EPS, 1));
            }
          } else if (nret.size() == 2) {
            double d1 = abs(ps[i] - nret[0]);
            double d2 = abs(ps[i] - nret[1]);
            if (d1 > d2) { swap(d1, d2); }
            events.push_back(make_pair(d1 - EPS, 1));
            events.push_back(make_pair(d2 + EPS, -1));
          }
        }
        sort(events.begin(), events.end());
        int begin = 0;
        FORIT(it, events) {
          if (begin && cnt == 0) { goto next; }
          if (it->second == 0) { break; }
          if (it->second == 2) { begin = 1; continue; }
          if (it->second == 1) {
            cnt++;
          } else if (it->second == -1) {
            cnt--;
          }
        }
        g[i].push_back(Edge(i, j, d));
        g[j].push_back(Edge(j, i, d));
next:;
      }
    }
    double ans = Dijkstra(g, 0, 1);
    printf("%.8f\n", ans);
  }
}

Measured memory_bytes: 1156