#include <bits/stdc++.h>
template<typename T>
struct Edge {
    int from, to;
    T cost;
    Edge(int from, int to, T cost) {
        this->from = from;
        this->to = to;
        this->cost = cost;
    }
};
bool operator == (Edge<int> e1, Edge<int> e2) {
    return e1.from == e2.from &&
            e1.to == e2.to &&
            e1.cost == e2.cost;
}
bool operator > (Edge<int> e1, Edge<int> e2) {
    return e1.cost < e2.cost;
}
template<typename T>
using Edges = std::vector<Edge<T>>;
template<typename T>
using Graph = std::vector<Edges<T>>;
template <typename T>
std::vector<T> dijkstra(const Graph<T> &g, int s) {
    int sz = (int)(g.size());
    std::vector<T> dist(sz, -1);
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()) {
        T d = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if(dist[now] == -1 || d > dist[now]) continue;
        for(int i=0;i<(int)(g[now].size());++i) {
            int next = g[now][i].to;
            T cost = g[now][i].cost;
            if(dist[next] == -1 || dist[next] > dist[now] + cost) {
                dist[next] = dist[now] + cost;
                pq.push({cost, next});
            }
        }
    }
    return dist;
}
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
using Point = std::complex<ld>;
const ld pi = acos(-1.0);
namespace std {
bool operator<(const Point &lhs, const Point &rhs) {
  if (lhs.real() < rhs.real() - eps) return true;
  if (lhs.real() > rhs.real() + eps) return false;
  return lhs.imag() < rhs.imag();
}
}
Point input_point() {
  ld x, y;
  std::cin >> x >> y;
  return Point(x, y);
}
bool eq(ld a, ld b) { return (abs(a - b) < eps); }
ld dot(Point a, Point b) { return real(conj(a) * b); }
ld cross(Point a, Point b) { return imag(conj(a) * b); }
int ccw(Point a, Point b, Point c) {
  b -= a;
  c -= a;
  if (cross(b, c) > eps) return 1;
  if (cross(b, c) < -eps) return -1;
  if (dot(b, c) < 0) return 2;
  if (norm(b) < norm(c)) return -2;
  return 0;
}
class Line {
 public:
  Point a, b;
  Line() : a(Point(0, 0)), b(Point(0, 0)) {}
  Line(Point a, Point b) : a(a), b(b) {}
};
ld dot(Line l, Line m) { return dot((l.a - l.b), (m.a - m.b)); }
bool isis_ll(Line l, Line m) { return !eq(cross(l.b - l.a, m.b - m.a), 0); }
bool isis_ls(Line l, Line s) {
  return isis_ll(l, s) &&
         (cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}
bool isis_ss(Line s, Line t) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
         ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
bool isis_lp(Line l, Point p) { return (abs(cross(l.b - p, l.a - p)) < eps); }
bool isis_sp(Line s, Point p) {
  return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}
Point proj(Line l, Point p) {
  ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
  return l.a + t * (l.a - l.b);
}
Point is_ll(Line l, Line m) {
  Point lv = l.b - l.a, mv = m.b - m.a;
  assert(cross(lv, mv) != 0);
  return l.a + lv * cross(mv, m.a - l.a) / cross(mv, lv);
}
ld dist_lp(Line l, Point p) { return abs(p - proj(l, p)); }
ld dist_ll(Line l, Line m) { return isis_ll(l, m) ? 0 : dist_lp(l, m.a); }
ld dist_ls(Line l, Line s) {
  return isis_ls(l, s) ? 0 : std::min(dist_lp(l, s.a), dist_lp(l, s.b));
}
ld dist_sp(Line s, Point p) {
  Point r = proj(s, p);
  return isis_sp(s, r) ? abs(r - p) : std::min(abs(s.a - p), abs(s.b - p));
}
ld dist_ss(Line s, Line t) {
  if (isis_ss(s, t)) return 0;
  return std::min(
      {dist_sp(s, t.a), dist_sp(s, t.b), dist_sp(t, s.a), dist_sp(t, s.b)});
}
Line bisector(Point a, Point b) {
  Point mid = (a + b) * Point(0.5, 0);
  return Line(mid, mid + (b - a) * Point(0, pi / 2));
}
ld degree_ll(Line l, Line m) {
  ld cos_shita = dot(l, m) / (abs(l.b - l.a) * abs(m.b - m.a));
  if (cos_shita < -1.0) cos_shita = -1.0;
  if (cos_shita > 1.0) cos_shita = 1.0;
  ld shita = acos(cos_shita);
  return shita;
}
class Circle {
 public:
  Point p;
  ld r;
  Circle() : p(Point(0, 0)), r(0) {}
  Circle(Point p, ld r) : p(p), r(r) {}
};
std::vector<Point> is_cc(Circle c1, Circle c2) {
  std::vector<Point> res;
  ld d = abs(c1.p - c2.p);
  ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
  ld dfr = c1.r * c1.r - rc * rc;
  if (abs(dfr) < eps)
    dfr = 0.0;
  else if (dfr < 0.0)
    return res;
  ld rs = sqrt(dfr);
  Point diff = (c2.p - c1.p) / d;
  res.emplace_back(c1.p + diff * Point(rc, rs));
  if (dfr != 0.0) res.emplace_back(c1.p + diff * Point(rc, -rs));
  return res;
}
std::vector<Point> is_lc(Circle c, Line l) {
  std::vector<Point> res;
  ld d = dist_lp(l, c.p);
  if (d < c.r + eps) {
    ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d);
    Point nor = (l.a - l.b) / abs(l.a - l.b);
    res.emplace_back(proj(l, c.p) + len * nor);
    res.emplace_back(proj(l, c.p) - len * nor);
  }
  return res;
}
std::vector<Point> is_sc(Circle c, Line l) {
  std::vector<Point> v = is_lc(c, l), res;
  for (Point p : v)
    if (isis_sp(l, p)) res.emplace_back(p);
  return res;
}
std::vector<Line> tangent_cp(Circle c, Point p) {
  std::vector<Line> ret;
  Point v = c.p - p;
  ld d = abs(v);
  ld l = sqrt(norm(v) - c.r * c.r);
  if (isnan(l)) {
    return ret;
  }
  Point v1 = v * Point(l / d, c.r / d);
  Point v2 = v * Point(l / d, -c.r / d);
  ret.emplace_back(Line(p, p + v1));
  if (l < eps) return ret;
  ret.emplace_back(Line(p, p + v2));
  return ret;
}
void solve(int n) {
  vector<Circle> circles;
  for(int i=0;i<n;++i) {
    Point p = input_point();
    ld r; cin >> r;
    circles.emplace_back(Circle(p, r));
  }
  Point s = circles[0].p, g = circles[n-1].p;
  vector<Point> p0(n-1), p1(n-1);
  for(int i=0;i<n-1;++i) {
    auto res = is_cc(circles[i], circles[i+1]);
    p0[i] = res[0];
    p1[i] = res[1];
  }
  Graph<ld> graph(2*n);
  Line line(s, g);
  bool ok = true;
  for(int i=0;i<n-1;++i) {
    ld lp0 = cross(line.b - line.a, p0[i] - line.a), lp1 = cross(line.b - line.a, p1[i] - line.a);
    ok &= (signbit(lp0) != signbit(lp1));
  }
  if(ok) graph[0].push_back(Edge<ld>(0, 2*n-1, abs(s - g)));
  for(int i=0;i<n-1;++i) {
    Line l0(s, p0[i]), l1(s, p1[i]);
    bool ok0 = true, ok1 = true;
    for(int j=0;j<i;++j) {
      ld l0p0 = cross(l0.b - l0.a, p0[j] - l0.a), l0p1 = cross(l0.b - l0.a, p1[j] - l0.a);
      ld l1p0 = cross(l1.b - l1.a, p0[j] - l1.a), l1p1 = cross(l1.b - l1.a, p1[j] - l1.a);
      ok0 &= (signbit(l0p0) != signbit(l0p1));
      ok1 &= (signbit(l1p0) != signbit(l1p1));
    }
    if(ok0) graph[0].push_back(Edge<ld>(0, 1 + i*2, abs(s - p0[i])));
    if(ok1) graph[0].push_back(Edge<ld>(0, 2 + i*2, abs(s - p1[i])));
  }
  for(int i=0;i<n-1;++i) {
    Line l0(p0[i], g), l1(p1[i], g);
    bool ok0 = true, ok1 = true;
    for(int j=i+1;j<n-1;++j) {
      ld l0p0 = cross(l0.b - l0.a, p0[j] - l0.a), l0p1 = cross(l0.b - l0.a, p1[j] - l0.a);
      ld l1p0 = cross(l1.b - l1.a, p0[j] - l1.a), l1p1 = cross(l1.b - l1.a, p1[j] - l1.a);
      ok0 &= (signbit(l0p0) != signbit(l0p1));
      ok1 &= (signbit(l1p0) != signbit(l1p1));
    }
    if(ok0) graph[1+i*2].push_back(Edge<ld>(1+i*2, 2*n-1, abs(g - p0[i])));
    if(ok1) graph[2+i*2].push_back(Edge<ld>(2+i*2, 2*n-1, abs(g - p1[i])));
  }
  for(int i=0;i<n-2;++i) {
    for(int j=i+1;j<n-1;++j) {
      Line l0(p0[i], p0[j]), l1(p0[i], p1[j]), l2(p1[i], p0[j]), l3(p1[i], p1[j]);
      bool ok0 = true, ok1 = true, ok2 = true, ok3 = true;
      for(int k=i+1;k<j;++k) {
        ld l0p0 = cross(l0.b - l0.a, p0[k] - l0.a), l0p1 = cross(l0.b - l0.a, p1[k] - l0.a);
        ld l1p0 = cross(l1.b - l1.a, p0[k] - l1.a), l1p1 = cross(l1.b - l1.a, p1[k] - l1.a);
        ld l2p0 = cross(l2.b - l2.a, p0[k] - l2.a), l2p1 = cross(l2.b - l2.a, p1[k] - l2.a);
        ld l3p0 = cross(l3.b - l3.a, p0[k] - l3.a), l3p1 = cross(l3.b - l3.a, p1[k] - l3.a);
        ok0 &= (signbit(l0p0) != signbit(l0p1));
        ok1 &= (signbit(l1p0) != signbit(l1p1));
        ok2 &= (signbit(l2p0) != signbit(l2p1));
        ok3 &= (signbit(l3p0) != signbit(l3p1));
      }
      if(ok0) graph[1+i*2].push_back(Edge<ld>(1+i*2, 1+j*2, abs(p0[i] - p0[j])));
      if(ok1) graph[1+i*2].push_back(Edge<ld>(1+i*2, 2+j*2, abs(p0[i] - p1[j])));
      if(ok2) graph[2+i*2].push_back(Edge<ld>(2+i*2, 1+j*2, abs(p1[i] - p0[j])));
      if(ok3) graph[2+i*2].push_back(Edge<ld>(2+i*2, 2+j*2, abs(p1[i] - p1[j])));
    }
  }
  cout << dijkstra(graph, 0)[2*n-1] << endl;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  while(1) {
    int n; cin >> n;
    if(n == 0) break;
    solve(n);
  }
}



Measured memory_bytes: 3508