#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
#include <cfloat>
 
using namespace std;
 
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()
#define eps 10e-5
#define INF 1e8
 
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;
 
 
#define M INT_MAX
 
//Point
struct P{
    double x, y;
    P(){ x=M; y=M;}
 
    P(const double &s , const double &e)
    {x=s; y=e;}
 
    P operator - (const P &t) const
    { return P(x-t.x , y-t.y);}
 
    P operator + (const P &t) const
    { return P(x+t.x , y+t.y); }
 
    P operator * (const double &d) const
    { return P(x*d , y*d); }
};
 
 
//Line
double dis(P t);
struct L{
    P p1,p2;
 
    L(){}
 
    L(const P &s , const P &e)
        { p1=s; p2=e;}
    double ldis(){
        return dis(p1-p2);
    }
};
  
//Circle
struct C{
    P a;
    double r;
    C(){}
    C(const P &s , const double &e)
        { a=s; r=e;}
};
 
//距離を求める
double dis(P t){
    return sqrt(t.x*t.x+t.y*t.y);
}
 
//単位ベクトルを求める
P unit_vector(P t){
    double u=fabs(dis(t));
    return P(t.x/u , t.y/u);
}
 
//外積を求める a×b
double cross(P a,P b){
    return (a.x*b.y-a.y*b.x);
}
 
//線分交差判定
bool intersect_s(P a1 , P a2 , P b1 , P b2){
    return ( cross(a2-a1 , b1-a1)*cross(a2-a1 , b2-a1) < eps) &&
           ( cross(b2-b1 , a1-b1)*cross(b2-b1 , a2-b1) < eps);
}
 
//点pを中心としてr(radian)回転       p(0,0)で原点を中心として回転
P rotate(P t , P p , double r){
    //double r=radians(angle);
    double ta=cos(r)*(t.x-p.x)-sin(r)*(t.y-p.y)+p.x;
    double tb=sin(r)*(t.x-p.x)+cos(r)*(t.y-p.y)+p.y;
    return P(ta , tb);
}
  
//応用
//２円 |x-a|=raと|x-b|=rbの交点計算
L interpoint_cc(C a , C b){
    double di=fabs(dis(a.a-b.a));
    if(di > a.r+b.r || di < fabs(a.r-b.r)) return L(P(0, 0), P(0, 0));
    double t=(a.r*a.r-b.r*b.r+di*di)/(di+di);
    double rd=acos(t/a.r);
  
    P dv=unit_vector(b.a-a.a);
    P g1=rotate(dv , P(0,0) , rd);
    P g2=rotate(dv , P(0,0) , -rd);
    return L(a.a+g1*a.r, a.a+g2*a.r);
}
 
 
class State{
public:
        C c;
    L l;
        double s1, s2;
    State(){}
    State(C cc, L ll){c = cc; l = ll;}
};
 
 
 
State dp[110];
 
bool check(L l, int s, int t){
    for(s++;s<t;s++) if(!intersect_s(l.p1, l.p2, dp[s].l.p1, dp[s].l.p2))return 0;
    return 1;
}
 
 
 
int main(void){
    int n;
    while(cin>>n, n){
        memset(dp, 0, sizeof(dp));
        REP(i,110) dp[i].s1 = dp[i].s2 = INF;
        int x, y;
        double r;
        cin >> x >> y >> r;
        State s = State(C(P(x,y),r), L(P(x,y),P(x,y)));
        dp[0] = s;
        dp[0].s1 = dp[0].s2 = 0;
        for(int i = 1; i < n; i++){
            cin >>x>>y>>r;
            C c = C(P(x,y),r);
            State s = State(c, interpoint_cc(c, dp[i-1].c));
            s.s1 = s.s2 = INF;
            dp[i] = s;
            REP(k,i){
                L l1 = L(dp[k].l.p1, dp[i].l.p1);
                if(dp[k].s1 != INF && check(l1, k, i)){
                    dp[i].s1 = min(dp[i].s1, dp[k].s1 + l1.ldis());
                }
                L l2 = L(dp[k].l.p2, dp[i].l.p1);
                if(dp[k].s2 != INF && check(l2, k, i)){
                    dp[i].s1 = min(dp[i].s1, dp[k].s2 + l2.ldis());
                }
                l1 = L(dp[k].l.p1, dp[i].l.p2);
                if(dp[k].s1 != INF && check(l1, k, i)){
                    dp[i].s2 = min(dp[i].s2, dp[k].s1 + l1.ldis());
                }
                l2 = L(dp[k].l.p2, dp[i].l.p2);
                if(dp[k].s2 != INF && check(l2, k, i)){
                    dp[i].s2 = min(dp[i].s2, dp[k].s2 + l2.ldis());
                }
            }
        }
/*
        REP(i,n){
        	printf("%.9f %0.9f\n", dp[i].s1, dp[i].s2);
        }
*/
	REP(k,n){
            L l1 = L(dp[k].l.p1, dp[n-1].c.a);
            if(dp[k].s1 != INF && check(l1, k, n)){
//printf("dp[%d] : min(%.9f, %.9f + %.9f)\n", k, dp[n].s1, dp[k].s1, l1.ldis());
                dp[n].s1 = min(dp[n].s1, dp[k].s1 + l1.ldis());
            }
            L l2 = L(dp[k].l.p2, dp[n-1].c.a);
            if(dp[k].s2 != INF && check(l2, k, n)){
//printf("dp[%d] : min(%.9f, %.9f + %.9f)\n", k, dp[n].s1, dp[k].s2, l2.ldis());
                dp[n].s1 = min(dp[n].s1, dp[k].s2 + l2.ldis());
            }
        }
        printf("%.9f\n", dp[n].s1);
    }
 
    return 0;
}

Measured memory_bytes: 1328