#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define inf 100000000
#define eps (1e-11)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

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

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1,Point p2):p1(p1),p2(p2){}
};
typedef Segment Line;

class Circle{
public:
  Point c;
  double r;
  Circle(Point c=Point(),double r=0.0):c(c),r(r){}
};

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}
double arg(Vector p){ return atan2(p.y,p.x);}
Vector polar(double a,double r){ return Point(cos(r)*a,sin(r)*a);}


static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;

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(a.norm()<b.norm())return ONLINE_FRONT;
  return ON_SEGMENT;
}

bool intersect(Point p1,Point p2,Point p3,Point p4){
  return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0 &&
          ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}

bool intersect(Segment s1,Segment s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

pair<Point,Point> getCrossPoints(Circle c1,Circle c2){
  double d=abs(c1.c-c2.c);
  double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
  double t=arg(c2.c-c1.c);
  return mp(c1.c+polar(c1.r,t+a),c1.c+polar(c1.r,t-a));
}

int main()
{
  int n;
  Point p[150][2];
  double dp[150][2];
  Circle C[101];

  while(1){
    cin>>n;
    if(n==0)break;
    for(int i=0;i<n;i++)cin>>C[i].c.x>>C[i].c.y>>C[i].r;
    for(int i=0;i<150;i++){
      dp[i][0]=inf;
      dp[i][1]=inf;
    }

    p[0][0]=C[0].c; // ?§????
    p[0][1]=C[0].c;

    //  ????????????????????????
    for(int i=1;i<n;i++){
      pair<Point,Point> pp=getCrossPoints(C[i-1],C[i]);
      p[i][0]=pp.f;
      p[i][1]=pp.s;
    }
    p[n][0]=C[n-1].c; // ??????
    p[n][1]=Point(inf,inf);

    dp[0][0]=0;
    for(int i=1;i<=n;i++){
      for(int j=0;j<2;j++){
	for(int k=i-1;k>=0;k--){
	  for(int l=0;l<2;l++){
	    bool flag=true;
	    Segment S=Segment(p[i][j],p[k][l]);
	      for(int c=k+1;c<i;c++){
		if(!intersect(Segment(p[c][0],p[c][1]),S))flag=false;
	      }
	    if(flag){
	      dp[i][j]=min(dp[i][j],dp[k][l]+abs(S.p1-S.p2));
	    }
	  }
	}
      }
    }
    printf("%.10f\n",dp[n][0]);
  }
  return 0;
}