#include <cstdio>
#include <algorithm>
 
// double
struct P{
    P(){}
    P(double _r, double _i):r(_r), i(_i){}
    void real(const double& v){r = v;}
    void imag(const double& v){i = v;}
    double r, i;
};
 
double real(const P& p){return p.r;}
double imag(const P& p){return p.i;}
double norm(const P& p){double r = real(p), i = imag(p); return r * r + i * i;}
double dist(const P& p){return std::sqrt(norm(p));}
 
P operator+(const P& lhs, const P& rhs){
    return P(real(lhs)+real(rhs), imag(lhs)+imag(rhs));
}
P operator-(const P& lhs, const P& rhs){
    return P(real(lhs)-real(rhs), imag(lhs)-imag(rhs));
}
P operator-(const P& p){
    return P(-real(p), -imag(p));
}
 
double cross(const P& lhs, const P& rhs){
    return real(lhs)*imag(rhs) - imag(lhs)*real(rhs);
}
 
double dot(const P& lhs, const P& rhs){
    return real(lhs)*real(rhs) + imag(lhs)*imag(rhs);
}
 
bool areIntersectedLines(const P& p1, const P& p2, const P& q1, const P& q2){
    if(cross(p1-p2, q1-p2) == 0 && dot(p1-p2, q1-p2) > 0 &&
       0 <= norm(q1-p2) && norm(q1-p2) <= norm(p1-p2)){
        return true;
    }
    if(cross(p1-p2, q2-p2) == 0 && dot(p1-p2, q2-p2) > 0 &&
       0 <= norm(q2-p2) && norm(q2-p2) <= norm(p1-p2)){
        return true;
    }
    if(cross(q1-q2, p1-q2) == 0 && dot(q1-q2, p1-q2) > 0 &&
       0 <= norm(p1-q2) && norm(p1-q2) <= norm(q1-q2)){
        return true;
    }
    if(cross(q1-q2, p2-q2) == 0 && dot(q1-q2, p2-q2) > 0 &&
       0 <= norm(p2-q2) && norm(p2-q2) <= norm(q1-q2)){
        return true;
    }
 
    return (cross(p1-p2, q1-p2) * cross(p1-p2, q2-p2) < 0) &&
        (cross(q1-q2, p1-q2) * cross(q1-q2, p2-q2) < 0);
}
 
int N;
P ps[100], is[101][2];
double rs[100], dp[101][2];
 
double rec(int index, int which){
    if(index == N){return 0.0;}
    if(dp[index][which] > 0.0){return dp[index][which];}
     
    double res = 1e20;
    for(int i=index+1;i<=N;i++){
        for(int w=0;w<2;w++){
            int j;
            for(j=index+1;j<i;j++){
                if(!areIntersectedLines(is[index][which], is[i][w], is[j][0], is[j][1])){
                    break;
                }
            }
 
            if(j == i){res = std::min(res, rec(i, w) + dist(is[index][which] - is[i][w]));}
        }
    }
 
    return dp[index][which] = res;
}
 
int main(){
    while(scanf("%d", &N), N){
        for(int i=0;i<=N;i++){
            for(int j=0;j<2;j++){
                dp[i][j] = -1.0;
            }
        }
     
        for(int i=0;i<N;i++){
            double x, y;
            scanf("%lf %lf %lf", &x, &y, rs+i);
 
            ps[i].real(x);
            ps[i].imag(y);
        }
 
        is[0][0] = ps[0];
        is[N][0] = ps[N-1];
        is[N][1] = ps[N-1];
        for(int i=1;i<N;i++){
            P u = ps[i] - ps[i-1], v{-imag(u), real(u)};
            double d = dist(u);
            double x = 0.5 / d * (1.*d*d + rs[i-1]*rs[i-1] - rs[i]*rs[i]),
                y = std::sqrt(rs[i-1]*rs[i-1] - x*x);
         
            u = {real(u) / d * x, imag(u) / d * x};
            v = {real(v) / d * y, imag(v) / d * y};
         
            P w = u + v;
            is[i][0] = ps[i-1] + w;
 
            w = u - v;
            is[i][1] = ps[i-1] + w;
        }
 
        printf("%.6f\n", rec(0, 0));
    }
}

Measured memory_bytes: 1096