#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double R;//double long double ??????????????? cmath?????¢??°??????????????????????????????????????????????????§????????????
typedef complex<R> Point;
typedef pair<Point , Point> Line;
typedef pair<Point ,R > Circle;
typedef vector<Point> Poly;

#define EPS (1e-10)//??????
#define EQ(a,b) (abs((a)-(b)) < EPS)//??????????????°???????????????
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )//????????????????????????????????????

#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

int n;
Circle c[200];

R dot(Point a,Point b){
    return (a.real() * b.real() + a.imag() * b.imag());
}
R cross(Point a,Point b){
    return (a.real() * b.imag() - a.imag() * b.real());
}
bool is_intersection_two_line_segment(Line a,Line b){
    Point a1 = a.first,a2 = a.second,b1 = b.first,b2 = b.second;
    return ( cross(a2 - a1,b1 - a1) * cross(a2 - a1,b2 - a1) < EPS) && (cross(b2 - b1,a1 - b1) * cross(b2 - b1, a2 - b1) < EPS);
}

Line intersection_of_two_circles(Circle c1,Circle c2){//????????????????????????Line?????\????????????(r1 + r2 > sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2))???????????????????????????
    R a =  abs(c2.first - c1.first);
    R b = c1.second;
    R c = c2.second;

    R rc = (a  * a + b * b - c * c) / (2.0 * a);
    R rs = sqrt(b * b - rc * rc);//C++ ??§???????????????????????????????????§???????????????sqrt ????????? float ?????????????????? long double ????????????????????????????????????????????¨?????§???????????? C ????????°????????§??????sqrt ????????? double ??????????????£??????????????????
    Point diff = (c2.first - c1.first) / a;

    Line p ;
    p.first = c1.first + diff * rc + diff * Point(0,1) * rs;
    p.second = c1.first + diff * rc + diff * Point(0,-1) * rs;

    return p;
}

bool input(){
    scanf("%d",&n);

    if(n == 0)
        return false;
    REP(i,n){
        double re,im;
        cin >> re >> im  >> c[i].second;
        c[i].first = Point(re,im);
    }
    return true;
}

double G[1000][1000];
Point ver[200][2];

bool judgecross(Point a,Point b,int a1,int b1){
    Line c(a,b);
     FOR(i,a1+1,b1){
         Line d(ver[i][0],ver[i][1]);
         if(!is_intersection_two_line_segment(c,d))
             return false;
    }
    return true;
}


void solve(){
    REP(i,1000)
        REP(j,1000)
            G[i][j] = 1000000000.0;
    REP(i,1000)
        G[i][i] = 0.0;

    REP(i,n-1){
        Line inter = intersection_of_two_circles(c[i],c[i+1]);
        ver[i][0] = inter.first;
        ver[i][1] = inter.second;
    }
    //REP(i,n-1)
        //printf("%lf %lf    %lf %lf\n",ver[i][0].real(),ver[i][0].imag(),ver[i][1].real(),ver[i][1].imag());
    REP(i,(n - 1) * 2){
        FOR(j,i + 1,(n - 1) * 2){
            int i1 = i / 2;int i2 = i % 2;
            int j1 = j / 2;int j2 = j % 2;
            if(!judgecross(ver[i1][i2],ver[j1][j2],i1,j1))
                continue;
            G[i][j] = G[j][i] = abs(ver[i1][i2] - ver[j1][j2]);
        }
    }
    Point start(c[0].first.real(),c[0].first.imag());
    REP(i,(n - 1) * 2){
        int i1 = i / 2;int i2 = i % 2;
        if(!judgecross(start,ver[i1][i2],-1,i1))
            continue;
        G[i][n * 2 - 2]  = G[n * 2 - 2][i] = abs(start - ver[i1][i2]);
    }
    Point end(c[n-1].first.real(),c[n-1].first.imag());
    REP(i,(n - 1) * 2){
        int i1 = i / 2;int i2 = i % 2;
        if(!judgecross(ver[i1][i2],end,i1,n-1))
            continue;
        G[i][n * 2 - 1] = G[n * 2 - 1][i] = abs(end - ver[i1][i2]);
    }
    if(judgecross(start,end,-1,n-1))
        G[n * 2 - 1][n * 2 - 2] = G[n * 2 - 2][n * 2 - 1] = abs(start - end);
    REP(k,n*2){
        REP(i,n*2){
            REP(j,n*2){
                G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
            }
        }
    }
    printf("%lf\n",G[n*2-2][n*2-1]);
}

int main(){
    while(input()){
        solve();
    }
    return 0;
}

Measured memory_bytes: 11148