#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define R(i,a,n) for(int i=a;i<n;i++)
#define INF 1<<31
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)
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 a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  bool operator < (const Point &p) const{
    return x!=p.x?x<p.x:y<p.y;
  }
  bool operator == (const Point &p) const{
    return fabs(x-p.x)<EPS&&fabs(y-p.y)<EPS;
  }
};
struct Circle{
  Point c;
  double r;
};
typedef Point vect;
struct seg{Point p1,p2;};
//????????´????????????
double norm(Point p){return p.x*p.x+p.y*p.y;}
//??¶???????????????absolute  ?????????????????¶?????????
double abs(Point p){return sqrt(norm(p));}
//?????????????????????????????????
double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y;
}
//?????? ????????????????????????
double cross(Point a,Point b){
  return a.x*b.y-a.y*b.x;
}
//2???????????¢   ???????????????
double getDistancePP(Point a,Point b){
  return abs(a-b);
}
//??´??????????????¢(????°?)???????????????
double getDistanceLP(seg l,Point p){
  return abs(cross(l.p2-l.p1,p-l.p1)/abs(l.p2-l.p1));
}
//?????????????????¢??????????????????
double getDistanceSP(seg s,Point p){
  if(dot(s.p2-s.p1,p-s.p1)<0.0)return abs(p-s.p1);
  if(dot(s.p1-s.p2,p-s.p2)<0.0)return abs(p-s.p2);
  return getDistanceLP(s,p);
}
//????¨?????????????????¨??????????????????????????????????
int CCW(Point p0,Point p1,Point p2){
  Point a=p1-p0;
  Point b=p2-p0;
  if(cross(a,b)>EPS)return 1;
  if(cross(a,b)<-EPS)return -1;
  if(dot(a,b)<-EPS)return 2;
  if(norm(a)<norm(b))return -2;
  return 0;
}
//????????????????????????????????????????????§?\????
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(seg s1,seg s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
//??????????????¢?????????????????????????????§??¨???????????????
double getDistance(seg s1,seg s2){
  if(intersect(s1,s2))return 0.0;
  return min(min(getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2)),
    min(getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2)));
}
//2??????????????????
double arg(Point p){return atan2(p.y,p.x);}
Point polar(double a,double r){return Point(cos(r)*a,sin(r)*a);}
seg getCrossPoints(Circle c1,Circle c2){
  //assert(intersect(c1,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);
  seg s;s.p2=c1.c+polar(c1.r,t+a);s.p1=c1.c+polar(c1.r,t-a);
  return s;
}
/////------Library END-------//////////////////////////////////////
int main(){
  int n;
  while(cin>>n,n){
    Point p[n*2];int gg=0,j=1;
    Circle c[n];
    seg a[n-1],s,t;
    r(i,n)cin>>c[i].c.x>>c[i].c.y>>c[i].r;
    r(i,n-1)a[i]=getCrossPoints(c[i],c[i+1]);
    for(int i=0;i<n-1;i++){
      p[j]=a[i].p1;j++;
      p[j]=a[i].p2;j++;
    }p[0]=c[0].c;p[n*2-1]=c[n-1].c;
    s.p1=c[0].c;s.p2=c[n-1].c;
    double w[n*2][n*2];//
    r(i,n*2)r(j,n*2)w[i][j]=10000000;
    R(i,0,n*2){
      R(j,i,n*2){
        int q1,q2,cc=0;
        r(k,n-1){if(p[i]==a[k].p1||p[i]==a[k].p2){q1=k;break;}}
        r(k,n-1){if(p[j]==a[k].p1||p[j]==a[k].p2){q2=k;break;}}
        if(!i)q1=0;
        if(j==n*2-1)q2=n-1;
        else q2++;
        s.p1=p[i];s.p2=p[j];int ju=q2-q1;
        R(k,0,n-1)if(intersect(s,a[k]))cc++;
        if(cc>=ju)w[i][j]=w[j][i]=getDistancePP(p[i],p[j]);
      }
    }
    r(k,n*2)r(i,n*2)r(j,n*2)w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
    printf("%.11f\n",w[0][n*2-1]);
    
  }
}

Measured memory_bytes: 3992