#include <vector>
#include <cassert>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <complex>
#include <cstdio>
#include <queue>
using namespace std;

const double EPS = 1e-8;
const double INF =  1e12;
const double PI = acos(-1);
typedef complex<double> P;
bool operator<(const P &a, const P&b) {
  return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
double cross(const P &a, const P&b) {
  return imag(conj(a)*b);
}
double dot(const P &a, const P&b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
struct C {
  P p; double r;
  C(const P &p, double r) : p(p), r(r) {}
  C() {}
};

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if(cross(b,c) > 0) return 1;
  if (cross(b,c) < 0) return -1;
  if (dot(b,c) < 0) return 2;
  if (norm(b) < norm(c)) return -2;
  return 0;
}
P projection(const L &l, const P &p) {
  double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
  return l[0] + t*(l[0]-l[1]);
}
vector<P> crosspointLC(const L &l, const C &c) {
  vector<P> ret;
  P 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; }
  P vect = (l[1]-l[0]);
  vect /= abs(vect);
  ret.push_back(center-vect*t);
  if (t > EPS) {
    ret.push_back(center+vect*t);
  }
  assert(ret.size() == 2);
  return ret;
}

vector<P> crosspointCC(const C &c1, const C &c2) {
  vector<P> ret;
  double d = abs(c1.p-c2.p);
  if (max(c1.r,c2.r) - min(c1.r,c2.r) - d > -EPS) {
    assert(0);
    return ret;
  }
  double x = (d*d+c1.r*c1.r-c2.r*c2.r) / (2*d);
  P start = c1.p + (c2.p-c1.p) / d * x;
  P vect = (c1.p-c2.p) * P(0,1);
  return crosspointLC(L(start, start + vect), c1);
}

typedef double Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) {}
};

bool operator<(const Edge &a, const Edge &b) {
  return a.weight != b.weight ? a.weight > b.weight :
    a.src != b.src ? a.src < b.src : a.dst < b.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void dijkstra(const Graph &g, int s,vector<Weight> &dist, vector<int> &prev) {
  const int n = g.size();
  dist.resize(n);
  prev.resize(n);
  for (int i=0; i<n; ++i) {
    dist[i] = 1e9;
    prev[i] = -1;
  }
  priority_queue<Edge> q;
  q.push(Edge(-2, s, 0));
  dist[s] = 0;
  while(!q.empty()) {
    Edge e = q.top(); q.pop();
    if (prev[e.dst] != -1) continue;
    prev[e.dst] = e.src;

    for (int i=0; i<g[e.dst].size(); ++i) {
      int w = g[e.dst][i].dst;
      if (dist[w] > dist[e.dst] + g[e.dst][i].weight) {
        dist[w] = dist[e.dst] + g[e.dst][i].weight;
        q.push(Edge(e.dst,w,dist[w]));
      }
    }
  }
}

C circle[100];
P cps[100][2];

bool ok(int s, int t, const L &l) {
  for (int i=s; i<=t; ++i) {
    if (ccw(l[0], l[1], cps[i][0]) ==-1) return 0;
    if (ccw(l[0], l[1], cps[i][1]) ==1) return 0;
  }
  return 1;
}

void add_edge(Graph &g, int s, int t, Weight d) {
  //cout << s << " " << t <<  " "  << d << endl;
  g[s].push_back(Edge(s, t, d));
  g[t].push_back(Edge(t,s,d));
}
int main() {
  int n;
  while(cin>>n , n) {
    for (int i=0; i<n; ++i) {
      double x, y, r;
      cin >> x >> y >> r;
      circle[i] = C(P(x,y),r);
    }
    for (int i=0; i<n-1; ++i) {
      vector<P> ret = crosspointCC(circle[i], circle[i+1]);
      if (ccw(circle[i].p, circle[i+1].p,ret[0]) == -1) {
        swap(ret[0], ret[1]);
      }
      cps[i][0] = ret[0];
      cps[i][1] = ret[1];
    }
    Graph g((n-1)*2+2);
    for (int i=0; i<n-1; ++i) {
      for (int j=i+1; j<n-1; ++j) {
        if (ok(i,j,L(cps[i][0], cps[j][0]))) add_edge(g, i*2, j*2, abs(cps[i][0]-cps[j][0]));
        if (ok(i,j,L(cps[i][0], cps[j][1]))) add_edge(g, i*2, j*2+1, abs(cps[i][0]-cps[j][1]));
        if (ok(i,j,L(cps[i][1], cps[j][0]))) add_edge(g, i*2+1, j*2, abs(cps[i][1]-cps[j][0]));
        if (ok(i,j,L(cps[i][1], cps[j][1]))) add_edge(g, i*2+1, j*2+1, abs(cps[i][1]-cps[j][1]));
      }
    }
    for (int i=0; i<n-1; ++i) {
      if (ok(0,i,L(circle[0].p,cps[i][0]))) add_edge(g, (n-1)*2, i*2, abs(circle[0].p-cps[i][0]));
      if (ok(0,i,L(circle[0].p,cps[i][1]))) add_edge(g, (n-1)*2, i*2+1, abs(circle[0].p-cps[i][1]));
      if (ok(i,n-2,L(cps[i][0], circle[n-1].p))) add_edge(g, (n-1)*2+1, i*2, abs(circle[n-1].p-cps[i][0]));
      if (ok(i,n-2,L(cps[i][1], circle[n-1].p))) add_edge(g, (n-1)*2+1, i*2+1, abs(circle[n-1].p-cps[i][1]));
    }
    if (ok(0,n-2,L(circle[0].p, circle[n-1].p))) add_edge(g, (n-1)*2, (n-1)*2+1, abs(circle[0].p-circle[n-1].p));
    vector<Weight> dist;
    vector<int> prev;
    dijkstra(g, (n-1)*2, dist, prev);
    double ans = dist[(n-1)*2+1];
    printf("%.10f\n", ans);
  }
}

Measured memory_bytes: 1140