#include <bits/stdc++.h>

using namespace std;

#define MAX_N 110
#define INF 1e9
#define EPS 1e-10
#define equal(a,b) (fabs(a-b) < EPS)
#define not_equal(a,b) (!equal(a,b))
#define lt(a,b) (a-b < -EPS)

struct Point{
  double x,y;

  Point(){}
  Point(double x,double y) : x(x),y(y) {}

  Point operator + (const Point &p)const{ return Point(x+p.x,y+p.y); }
  Point operator - (const Point &p)const{ return Point(x-p.x,y-p.y); }
  Point operator * (const double &k)const{ return Point(x*k,y*k); }
  Point operator / (const double &k)const{ return Point(x/k,y/k); }
  bool operator < (const Point &p)const{ return x != p.x ? x < p.x : y < p.y; }
};

Point operator * (const Point &a,const Point &b){ return Point(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }

double dot(const Point &a,const Point &b){ return a.x*b.x+a.y*b.y; }
double cross(const Point &a,const Point &b){ return a.x*b.y - b.x*a.y; }
double norm(const Point &p){ return dot(p,p); }
double abs(const Point &p){ return sqrt(norm(p)); }
double getDistance(const Point &a,const Point &b){
  return sqrt(pow(a.x-b.x,2) + pow(a.y-b.y,2));
}

istream &operator >> (istream &is,Point &p){ 
  return is >> p.x >> p.y;
}

typedef Point Vector;

#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
typedef Point Vector;

int ccw(Point p0,Point p1,Point p2){
  Vector a = p1 - p0;
  Vector b = p2 - p0;
  if(cross(a,b) > EPS){ return COUNTER_CLOCKWISE; }
  if(cross(a,b) < -EPS){ return CLOCKWISE; }
  if(dot(a,b) < -EPS){ return ONLINE_BACK; }
  if(norm(a) < norm(b)){ return ONLINE_FRONT; }
  return ON_SEGMENT;
}

struct Segment{
  Point s,t;
  Segment(){}
  Segment(Point s,Point t) : s(s),t(t) {}
};

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

bool isIntersectSS(const Segment &a,const Segment &b){
  Point s[2] = {a.s,a.t}, t[2] = {b.s,b.t};
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0
    && ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}

vector<Point> crosspointCC(const Circle &a,const Circle &b){
  vector<Point> res;
  double d = abs(a.p-b.p);
  double rc = (a.r*a.r-b.r*b.r+d*d)/(2.0*d);
  double rs = sqrt(a.r*a.r-rc*rc);
  Point p = (b.p-a.p)/d;
  res.push_back(Point(a.p+p*Point(rc,-rs)));
  res.push_back(Point(a.p+p*Point(rc,rs)));
  return res;
}

struct P{
  double d;
  int n,p;
  P(double d,int n,int p) : d(d),n(n),p(p) {}
  bool operator < (const P &p)const{
    if(d != p.d){
      return d > p.d;
    }
  }
};

double dist[MAX_N][2][MAX_N][2];

double solve(int N,const vector<Circle> &cirs){
  double d[MAX_N][2];
  fill(d[0],d[0]+MAX_N*2,INF);
  d[0][0] = 0.0;

  priority_queue<P> Q;
  Q.push(P(0,0,0));

  while(!Q.empty()){
    P p = Q.top(); Q.pop();
    int idx = p.n,pos = p.p;
    if(lt(d[idx][pos],p.d)){ continue; }
    if(idx == N){ return p.d; }
    for(int i = idx+1 ; i <= N ; i++){
      for(int j = 0 ; j < 2 ; j++){
        if(dist[idx][pos][i][j] == INF){ continue; }
        if(p.d+dist[idx][pos][i][j] < d[i][j]){
          d[i][j] = p.d+dist[idx][pos][i][j];
          Q.push(P(d[i][j],i,j));
        }
      }
    }
  }
  return -1;
}

void init(int N){
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < 2 ; j++){
      for(int k = 0 ; k <= N ; k++){
        for(int l = 0 ; l < 2 ; l++){
          dist[i][j][k][l] = INF;
        }
      }
    }
  }
}

int main(){
  int N;
  while(cin >> N,N){
    vector<Point> G[MAX_N];
    vector<Circle> cirs(N);
    init(N);
    for(int i = 0 ; i < N ; i++){
      cin >> cirs[i].p >> cirs[i].r;
      if(i == 0){
        G[i].push_back(cirs[0].p);
        G[i].push_back(cirs[0].p);
      }else{
        vector<Point> cp = crosspointCC(cirs[i-1],cirs[i]);
        G[i].push_back(cp[0]); G[i].push_back(cp[1]);
      }
    }
    G[N].push_back(cirs[N-1].p);
    G[N].push_back(cirs[N-1].p);

    for(int i = 0 ; i < N ; i++){
      for(int j = i+1 ; j <= N ; j++){
        Point p1[2] = {G[i][0],G[i][1]};
        Point p2[2] = {G[j][0],G[j][1]};
        for(int k = 0 ; k < 2 ; k++){
          for(int l = 0 ; l < 2 ; l++){
            Segment a = Segment(p1[k],p2[l]);
            bool ok = true;
            for(int m = i ; m < j ; m++){
              Segment b = Segment(G[m][0],G[m][1]);
              if(!isIntersectSS(a,b)){
                ok = false;
                break;
              }
            }
            if(ok){
              dist[i][k][j][l] = getDistance(p1[k],p2[l]);
            }
          }
        }
      }
    }
    printf("%.8f\n",solve(N,cirs));
  }
  return 0;
}

Measured memory_bytes: 1616