#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#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--)
#define P pair<v2,v2>
int n;
int x[200],y[200],r[200];
struct v2{
    double x;
    double y;
    v2 operator + (v2 a){
        v2 r;
        r.x = this->x + a.x;
        r.y = this->y + a.y;
        return r;
    }
    v2 operator - (v2 a){
        v2 r;
        r.x = this->x - a.x;
        r.y = this->y - a.y;
        return r;
    }
    v2 operator * (double a){
        v2 r;
        r.x = this->x * a;
        r.y = this->y * a;
        return r;
    }
    v2 operator / (double a){
        v2 r;
        r.x = this->x / a;
        r.y = this->y / a;
        return r;
    }
};

v2 crossv[200][2];
double v2abs(v2 a){
    return sqrt(a.x * a.x + a.y * a.y);
}

v2 rot90plus(v2 a){
    v2 r;r.x = -a.y;r.y = a.x;
    return r;
}

v2 rot90minus(v2 a){
    v2 r;r.x = a.y;r.y = -a.x;
    return r;
}



P get_2crossv_of_circle(double x1,double y1,double r1,double x2,double y2,double r2){
    v2 c1,c2;
    c1.x = x1;c1.y = y1;c2.x = x2;c2.y = y2;
    double a = v2abs(c2 - c1);
    double b = r1;
    double c = r2;

    double rc = (a * a + b * b - c * c) / (2.0 * a);
    double rs = sqrt(b * b - rc * rc);
    v2 diff = (c2 - c1) / a;

    P p;
    p.first = c1 + diff * rc + (rot90plus(diff) * rs);
    p.second = c1 + diff * rc + (rot90minus(diff) * rs);

    return p;
}

bool judge(v2 a1,v2 a2,v2 b1,v2 b2){
    v2 a = a2 - a1;
    v2 c1 = b1 - a1;
    v2 c2 = b2 - a1;
    return (a.x * c1.y - a.y * c1.x) * (a.x * c2.y - a.y * c2.x) <= 0.0;
}

bool judgecross(v2 a,v2 b,int a1,int b1){
    for(int i = a1 + 1;i < b1;i++){
        if(!judge(a,b,crossv[i][0],crossv[i][1])){
            return false;
        }
    }
    return true;
}

bool input(){
    scanf("%d",&n);
    if(n == 0)
        return false;
    REP(i,n){
        scanf("%d%d%d",&x[i],&y[i],&r[i]);
    }
    return true;
}

double G[1000][1000];

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){
        P p = get_2crossv_of_circle(x[i],y[i],r[i],x[i + 1],y[i + 1],r[i + 1]);
        crossv[i][0] = p.first;
        crossv[i][1] = p.second;
    }

    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(crossv[i1][i2],crossv[j1][j2],i1,j1))
                continue;
            G[i][j] = G[j][i] = v2abs(crossv[i1][i2] - crossv[j1][j2]);
        }
    }
    v2 start;start.x = x[0];start.y = y[0];
    REP(i,(n - 1) * 2){
        int i1  = i / 2;int i2 = i % 2;
        if(!judgecross(start,crossv[i1][i2],-1,i1))
            continue;
        
        G[i][n * 2 - 2] = G[n * 2 - 2][i] = v2abs(start - crossv[i1][i2]);
    }
    v2 end;end.x = x[n - 1];end.y = y[n - 1];
    REP(i,(n - 1) * 2){
        int i1  = i / 2;int i2 = i % 2;
        if(!judgecross(crossv[i1][i2],end,i1,n - 1))
            continue;
        
        G[i][n * 2 - 1] = G[n * 2 - 1][i] = v2abs(end - crossv[i1][i2]);
    }
    if(judgecross(start,end,-1,n - 1))
        G[n * 2 - 1][n * 2 - 2] = G[n * 2 - 2][n * 2 - 1] = v2abs(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: 11032