#include <iostream>
#include <vector>
#include <complex>
#include <iomanip>
using namespace std;
#define EPS 1e-10

typedef complex<double> C;

const double PI = 4*atan(1.0);

bool eq(double a,double b)
{
  return (-EPS<a-b&&a-b<EPS);
}

namespace std
{
    bool operator < (const C a, const C b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
    //点をsetとかmapにつめたいとき(誤差を1e-10とか厳しくし過ぎるとバグる)
    // bool operator<(const C a, const C b){
    //     return abs(a.real()-b.real())>EPS ? a.real()<b.real()-EPS : a.imag()<b.imag()-EPS;
    // }
    bool operator==(const C a, const C b){
        return (eq(a.real(),b.real()) && eq(a.imag(),b.imag()));
    }
    bool operator!=(const C a, const C b){
        return !(a == b);
    }
}

struct L : public vector<C>
{
    L(){}
    L(const C a, const C b) {
        push_back(a); push_back(b);
    }
};
double dot(const C a, const C b)
{
    return real(conj(a)*b);
}
double cross(const C a, const C b)
{
    return imag(conj(a)*b);
}
int ccw(C a, C b, C c)
{
    b -= a; c -= a;
    if(cross(b, c) > 0)   return +1;       // counter clockwise
    if(cross(b, c) < 0)   return -1;       // clockwise
    if(dot(b, c) < 0)     return +2;       // c--a--b on line
    if(norm(b) < norm(c)) return -2;       // a--b--c on line
    return 0;   //b--a--c on line
}
L crosspointCC(const C c1, const double r1, const C c2, const double r2)
{
    C a = conj(c2-c1), b = (r2*r2-r1*r1-(c2-c1)*conj(c2-c1)), c = r1*r1*(c2-c1);
    C d = b*b-4.0*a*c;
    C z1 = (-b+sqrt(d))/(2.0*a)+c1, z2 = (-b-sqrt(d))/(2.0*a)+c1;
    return L(z1, z2);
}
bool intersectSS(const L& s, const L& 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;
}
int n;
int main(){
    while(cin >> n &&n!=0){
        vector<C>v(n);
        vector<double>r(n);
        for(int i=0;i<n;i++){
            double a,b;
            cin >> a >> b >> r[i];
            v[i] = C(a,b);
        }
        vector<L>l(n);
        for(int i=0;i<n-1;i++){
            l[i] = crosspointCC(v[i],r[i],v[i+1],r[i+1]);
        }
        vector<C>s(2*n);
        s[0] = v[0];
        s[2*n-1] = v[n-1];
        for(int i=0;i<n-1;i++){
            s[i*2+1] = l[i][0];
            s[i*2+2] = l[i][1];
        }
        vector<vector<double>  > g(2*n,vector<double>(2*n,100000000.0));
        for(int i=0;i<2*n;i++){
            g[i][i] = 0.0;
        }
        bool fflag = 1;
        for(int i=0;i<n-1;i++){
            L a = L(s[0],s[2*n-1]);
            if(!intersectSS(a,l[i])){
                fflag = 0;
            }
        }
        if(fflag){
            g[0][2*n-1] = abs(s[0]-s[2*n-1]);
            g[2*n-1][0] = abs(s[0]-s[2*n-1]);
        }
        for(int i=0;i<n-1;i++){
            L a = L(s[0],s[1+2*i]);
            bool flag = 1;
            for(int j=0;j<i;j++){
                if(!intersectSS(a,l[j])){
                    flag =0;
                }
            }
            if(flag){
                g[0][1+2*i]=abs(s[0]-s[1+2*i]);
                g[1+2*i][0]=abs(s[0]-s[1+2*i]);
            }
            a = L(s[0],s[2+2*i]);
            flag = 1;
            for(int j=0;j<i;j++){
                if(!intersectSS(a,l[j])){
                    flag =0;
                }
            }
            if(flag){
                g[0][2+2*i]=abs(s[0]-s[2+2*i]);
                g[2+2*i][0]=abs(s[0]-s[2+2*i]);
            }
        }
        for(int i=n-2;i>=0;i--){
            L a = L(s[2*n-1],s[1+2*i]);
            bool flag = 1;
            for(int j=n-2;j>i;j--){
                if(!intersectSS(a,l[j])){
                    flag =0;
                }
            }
            if(flag){
                g[2*n-1][1+2*i]=abs(s[2*n-1]-s[1+2*i]);
                g[1+2*i][2*n-1]=abs(s[2*n-1]-s[1+2*i]);
            }
            a = L(s[2*n-1],s[2+2*i]);
            flag = 1;
            for(int j=n-2;j>i;j--){
                if(!intersectSS(a,l[j])){
                    flag =0;
                }
            }
            if(flag){
                g[2*n-1][2+2*i]=abs(s[2*n-1]-s[2+2*i]);
                g[2+2*i][2*n-1]=abs(s[2*n-1]-s[2+2*i]);
            }
        }
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n-1;j++){
                for(int z=1;z<=2;z++){
                    for(int zz=1;zz<=2;zz++){
                    
                        L a = L(s[z+2*i],s[zz+2*j]);
                        bool flag =1;
                        for(int k=i+1;k<j;k++){
                            if(!intersectSS(l[k],a)){
                                flag = 0;
                            }
                        }
                        if(flag){
                            g[z+2*i][zz+2*j]=abs(s[z+2*i]-s[zz+2*j]);
                            g[zz+2*j][z+2*i]=abs(s[z+2*i]-s[zz+2*j]);
                        }
                    }
                }
            }
        }
        for(int k=0;k<2*n;k++){
            for(int i=0;i<2*n;i++){
                for(int j=0;j<2*n;j++){
                    g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
                }
            }   
        }
        cout <<fixed << setprecision(10) << g[0][2*n-1] << endl;
    }



    return 0;
}


Measured memory_bytes: 3560