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

typedef complex<double> P;
typedef pair<P,P> L;

const int N = 100;
const double EPS = 1e-8;
const double INF = 1 << 29;

struct Circle{
  P c; 
  double r;
  Circle(P c=P(0,0), double r=0):c(c),r(r){}
};

struct state{
  P p;
  double d;
  state(P p=P(0,0), double d=0):p(p),d(d){}
  bool operator < (const state &s) const {
    return d < s.d;
  }
};

double dot(P a, P b){ return real(conj(a)*b); }
double cross(P a, P b){ return imag(conj(a)*b); }

bool isIntersectSP(L s, P p){ 
  return abs(s.first-p) + abs(s.second-p) - abs(s.second-s.first) < EPS; 
}

P proj(P p, L l){
  return l.first + dot(p - l.first, l.second - l.first) / norm(l.second - l.first) * (l.second - l.first);
}

vector<P> getIntersectCS(Circle c, L s){
  vector<P> res;
  P h = proj(c.c, s);
  double d = abs(c.c - h);
  if(d > c.r + EPS);
  else if(d > c.r - EPS){
    if(isIntersectSP(s,h)) res.push_back(h);
  }
  else {
    P v = s.second - s.first;
    v = (sqrt(c.r*c.r - d*d) / abs(v)) * v;
    if(isIntersectSP(s, h+v)) res.push_back(h+v);
    if(isIntersectSP(s, h-v)) res.push_back(h-v);
  }
  return res;
}

vector<P> getIntersectCC(Circle c1, Circle c2){
  vector<P> res;
  double r1 = c1.r, r2 = c2.r, d;
  P p1 = c1.c, p2 = c2.c;
  d = abs(p1-p2);

  if(d < EPS && abs(r1-r2) < EPS) return res;
  if(r1 + r2 < d - EPS || d + EPS < abs(r1-r2)) return res;

  double a = (r1*r1 - r2*r2 + d*d) / (2*d);
  double h = sqrt(max(r1*r1 - a*a, 0.0));
  P tmp1 = p1 + a / d * (p2-p1);
  P tmp2 = h / d * (p2-p1);

  if(abs(tmp2) < EPS) res.push_back(tmp1);
  else {
    res.push_back(P(real(tmp1) - imag(tmp2), imag(tmp1) + real(tmp2)));
    res.push_back(P(real(tmp1) + imag(tmp2), imag(tmp1) - real(tmp2)));
  }
  return res;
}


int n;
vector<Circle> v;

bool isOk(P st, P go){
  vector<state> sv;
  
  for(int i=0;i<n;i++){
    vector<P> res = getIntersectCS(v[i], L(st,go));
    for(int j=0;j<res.size();j++){
      if(abs(res[j]-st) <= EPS || abs(res[j]-go) <= EPS) continue;
      sv.push_back(state(res[j], abs(res[j]-st)));
    }
  }
  sv.push_back(state(st, 0.0));
  sv.push_back(state(go, abs(st-go)));

  sort(sv.begin(), sv.end());

  for(int i=0;i<sv.size()-1;i++){
    P mid = (sv[i].p + sv[i+1].p) / 2.0;
    bool f = true;
    for(int j=0;j<n;j++){
      if(abs(mid - v[j].c) <= v[j].r + EPS){
        f = false;
        break;
      }
    }
    if(f) return false;
  }
  return true;
}

double solve(){
  double G[N*2+2][N*2+2];

  fill(G[0], G[n*2+2], INF);
  for(int i=0;i<n*2+2;i++) G[i][i] = 0;

  //??°????????????
  for(int i=0;i<n-1;i++){
    vector<P> res = getIntersectCC(v[i],v[i+1]);
    for(int j=i+1;j<n-1;j++){
      vector<P> res2 = getIntersectCC(v[j],v[j+1]);
      for(int k=0;k<res.size();k++){
        for(int l=0;l<res2.size();l++){
          if(!isOk(res[k], res2[l])) continue;
          G[2*i+k][2*j+l] = G[2*j+l][2*i+k] = min(G[2*i+k][2*j+l], abs(res[k] - res2[l]));
        }
      }
    }
    if(res.size() == 2){
      G[2*i][2*i+1] = G[2*i+1][2*i] = min(G[2*i][2*i+1], abs(res[0] - res[1]));
    }
    for(int j=0;j<res.size();j++){
      if(isOk(v[0].c, res[j])){
        G[2*n][2*i+j] = G[2*i+j][2*n] = min(G[2*n][2*i+j], abs(v[0].c - res[j]));
      }
      if(isOk(v[n-1].c, res[j])){
        G[2*n+1][2*i+j] = G[2*i+j][2*n+1] = min(G[2*n+1][2*i+j], abs(v[n-1].c - res[j]));
      }
    }
  }
  if(isOk(v[0].c, v[n-1].c)){
    G[2*n][2*n+1] = G[2*n+1][2*n] = min(G[2*n][2*n+1], abs(v[0].c - v[n-1].c));
  }

  //???????????£???????????????
  for(int k=0;k<2*n+2;k++){
    for(int i=0;i<2*n+2;i++){
      for(int j=0;j<2*n+2;j++){
        G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
      }
    }
  }

  return G[2*n][2*n+1];
}

int main(){
  while(cin >> n && n){
    v.clear();
    for(int i=0;i<n;i++){
      double x,y,r;
      cin >> x >> y >> r;
      v.push_back(Circle(P(x,y),r));
    }
    printf("%.7f\n",solve());
  }
}

Measured memory_bytes: 1616