#include <bits/stdc++.h>

using namespace std;


#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
 
struct Point{
    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); }
 
    double norm() {return x * x + y * y; }
    double abs() {return sqrt(norm()); }
 
    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);
    }
};
 
typedef Point Vector;
 
struct Circle{
    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 arg(Vector p){
    return atan2(p.y, p.x);
}
 
Vector polar(double a, double r){
    return Point(cos(r) * a, sin(r) * a);
}
 
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 make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
}
 /*
int main(){
    double c1x, c1y, c1r; cin>>c1x>>c1y>>c1r;
    double c2x, c2y, c2r; cin>>c2x>>c2y>>c2r;
 
    Circle c1 = {Point(c1x, c1y), c1r};
    Circle c2 = {Point(c2x, c2y), c2r};
 
    pair<Point, Point> ansp = getCrossPoints(c1, c2);
    Point p1 = min(ansp.first, ansp.second);
    Point p2 = max(ansp.first, ansp.second);
 
    printf("%.10f %.10f %.10f %.10f\n", p1.x, p1.y, p2.x, p2.y);
}
*/
int n;

double dist(double x1,double y1,double x2,double y2){
    return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)  );
}

bool judgeIenter(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy) {
    double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax);
    double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx);
    double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx);
    double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx);

   // return (tc * td < 0 && ta * tb < 0);
     return (tc * td <= 0 && ta * tb <= 0); // 端点を含む場合
}
double INF = 10000000;
double dp[110][2];
double d[110][3];
double p[110][2][2];
bool check(int a,int aa,int b,int bb){
    double ax,ay,bx,by;
    if(a == -1){
        ax = d[0][0];
        ay = d[0][1];
    }else{
        ax = p[a][aa][0];
        ay = p[a][aa][1];
    }
    if(b == n-1){
        bx = d[n-1][0];
        by = d[n-1][1];
    }else{
        bx = p[b][bb][0];
        by = p[b][bb][1];
    }
    bool flag = true;
    for(int i = max(0,a);i < b;i++){
      //  cout << judgeIenter(ax,ay,bx,by,p[i][0][0],p[i][0][1],p[i][1][0],p[i][1][1]) << ":";
    //    printf("%.2lf %.2lf %.2lf %.2lf %.2lf %.2lf %.2lf %.2lf\n",ax,ay,bx,by,p[i][0][0],p[i][0][1],p[i][1][0],p[i][1][1]);
        if(judgeIenter(ax,ay,bx,by,p[i][0][0],p[i][0][1],p[i][1][0],p[i][1][1]) == false){
            flag = false;
            break;
        } 
    }
    
    return (flag);
}



int main(){
 //   int n;
    while(true){
        cin >> n;
        if(n == 0)break;
        for(int i = 0;i <= n+1;i++){
            dp[i][0] = INF;
            dp[i][1] = INF;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 3;j++){
                cin >> d[i][j];
            }
        }
        for(int i = 0;i < n-1;i++){
            Circle c1 = {Point(d[i][0], d[i][1]), d[i][2]};
            Circle c2 = {Point(d[i+1][0], d[i+1][1]), d[i+1][2]};
            pair<Point, Point> ansp = getCrossPoints(c1, c2);
            p[i][0][0] = ansp.first.x;
            p[i][0][1] = ansp.first.y;
            p[i][1][0] = ansp.second.x;
            p[i][1][1] = ansp.second.y;
        //    printf("(%lf,%lf), (%lf,%lf)\n",p[i][0][0],p[i][0][1],p[i][1][0],p[i][1][1]);
        }
        for(int i = 0;i < 2;i++){
            dp[0][i] = dist(d[0][0],d[0][1],p[0][i][0],p[0][i][1]);
         //   printf("dp[0][%d] = %lf\n",i,dp[0][i]);
        }
        
        for(int i = 1;i < n-1;i++){
            for(int k = 0;k < 2;k++){
                double nx = p[i][k][0],ny = p[i][k][1];
                if(check(-1,0,i,k)) dp[i][k] = dist(d[0][0],d[0][1],nx,ny);
                for(int j = 0;j < i;j++){
                    for(int kk = 0;kk < 2;kk++){
                        if(check(j,kk,i,k))dp[i][k] = min(dp[i][k],dp[j][kk]+dist(p[j][kk][0],p[j][kk][1],nx,ny));
                    }
                }
            //    printf("dp[%d][%d] = %lf\n",i,k,dp[i][k]);
            }
        }
        double ans = INF;
        for(int i = -1;i < n-1;i++){
            for(int k = 0;k < 2;k++){
                if(check(i,k,n-1,0)){
                //    printf("i:%d,k:%d,ans=%lf\n",i,k,ans);
                    if(i == -1)ans = min(ans,dist(d[0][0],d[0][1],d[n-1][0],d[n-1][1]));
                    else ans = min(ans,dp[i][k]+dist(p[i][k][0],p[i][k][1],d[n-1][0],d[n-1][1]));
                }
            }
        }
        printf("%lf\n",ans);
     //   cout << ans << endl;
    }
}


Measured memory_bytes: 3664