#include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    Point operator + (Point p){
        return Point(x+p.x,y+p.y);
    }
  
    Point operator - (Point p){
        return Point(x-p.x,y-p.y);
    }
  
    Point operator * (double k){
        return Point(k*x,k*y);
    }
     
    Point operator * (Point p){
        return Point(p.x*x-p.y*y,p.x*y+p.y*x);
    }

    Point operator / (double k){
        return Point(x/k,y/k);
    }
    
    Point operator = (Point p){
        x = p.x;
        y = p.y;
        return *this;
    }

    bool operator<(const Point &p)const{
        return x!=p.x?x<p.x:y<p.y;
    }

};
double dot(Point p, Point q){
    return p.x*q.x+p.y*q.y;
}
  
double cross(Point p,Point q){
    return p.x*q.y-q.x*p.y;
}
  
double norm(Point p){
    //?????????????????§?????????2???
    return p.x*p.x+p.y*p.y;
}
  
double pabs(Point p){
    //?????????????????§??????
    return sqrt(norm(p));
}
Point UnitVector(Point a){
    //??????????????????
    return a/pabs(a);
}
typedef vector<Point> Polygon;
struct Line : Polygon{
    Line(){}
    Line(Point p,Point q){
        PB(p);
        PB(q);  
    }
};
struct Circle{
    Point p; //?????????
    double r; //??????
    Circle(){}
    Circle(Point _p,double _r){
        p = _p;
        r = _r;
    }
};
int ccw(Point a,Point b,Point c){
    b = b-a;
    c = c-a;
    if(cross(b,c) > 0)return +1; //a???b ??§???????¨?????????????c ccw
    if(cross(b,c) < 0)return -1; //a???b ??§????¨?????????????c ccw
    if(dot(b,c) < 0)return +2; // c--a--b;
    if(pabs(b)<pabs(c))return -2; //a--b--c
    return 0; //a--c--b
}

Point projection(Line l, Point p){
    double t = dot(p-l[0],l[0]-l[1]) / norm(l[0]-l[1]);
    return l[0] + (l[0]-l[1])*t;
}

Point reflection(Line l, Point p){
    return p + (projection(l,p)-p)*2.0; 
}

bool intersectSS(Line l,Line m){
    //l??¨m??????????????????????????????
    return (ccw(l[0],l[1],m[0])*ccw(l[0],l[1],m[1])<EPS)&&
            (ccw(m[0],m[1],l[0])*ccw(m[0],m[1],l[1])<EPS);
}

bool intersectSP(Line l, Point p){
    //??????l??¨???p?????????????????????
    return !ccw(l[0],l[1],p);
}

double distanceLP(Line l,Point p){
    //??????l??¨???p????????¢
    p = p - l[0];
    l[1] = l[1] - l[0];
    if(intersectSP(l,p))return 0.0;
    return fabs(cross(p,l[1])/pabs(l[1]));
}

bool intersectLL(Line l,Line m){
    return fabs(cross(l[1]-l[0],m[1]-m[0])) > EPS || //????????§??????
            fabs(cross(l[1]-l[0],m[0]-l[0])) < EPS; //????????????
}

bool intersectCP(Circle c,Point p){
    //???c??¨???p???????????????
    //true->???c????????¨??????p????????¨????????????.
    return fabs(pabs(p-c.p)-c.r)<EPS;
}

int intersectCL(Circle c,Line l,Point *p,Point *q){
    if(norm(projection(l,c.p) - c.p) - c.r*c.r > EPS)return 0;
    double d1 = pabs(c.p-l[0]);
    double d2 = pabs(c.p-l[1]);
    if(d1 < c.r + EPS && d2 < c.r + EPS)return 0;
    if(d1 < c.r - EPS && d2 > c.r+EPS
        || d1 > c.r + EPS && d2 < c.r -EPS)return 1;
    Point h = projection(l,c.p);
    if(dot(l[0] - h,l[1] - h) < 0)return 2;
    return 0;
}

int intersectCC(Circle a,Circle b,Point *p,Point *q){
    double dist = pabs(a.p-b.p);
    if(dist < fabs(a.r-b.r) || dist > a.r+b.r){
        //????????????????????´??????????????¨???
        //????????????????????¨???????????¨???
        *p = Point(1e15,1e15);
        *q = Point(1e15,1e15);
        return 0;
    }
    else if(fabs(dist-a.r-b.r) < EPS){
        //??????1?????§????????£???????????¨???
        Point way;
        way = b.p-a.p;
        *p = a.p+UnitVector(way)*a.r;
        *q = *p;
        return 1;
    }
    else{
        //??????2?????§????????£???????????¨???
        if(a.r < b.r){
            swap(a.r,b.r);
            swap(a.p,b.p);
        }
        double s = (a.r + b.r + dist) / 2.0 ;
        double area = sqrt(s * (s - a.r) * (s - b.r) * (s - dist));
        double h = 2.0 * area / dist;

        Point  v = b.p-a.p;
        v = UnitVector(v);
        Point  m = a.p + (v*sqrt(a.r*a.r-h*h));
        Point  n = v * Point(0.0,1.0);
        
        *p = m + (n * h);
        *q = m - (n * h);
        return 2;
    }
}

double TriangleArea(Point a,Point b,Point c){
    b = b - a;
    c = c - a;
    return cross(b,c)*0.5; //?????????????????¨??????????????§??¨???
}
 
double VertexArea(Polygon v){
    double subArea = 0.0;
    rep(i,v.size()-1){
        subArea += TriangleArea(v[0],v[i],v[i+1]);
    }
    return subArea; //?????????????????¨??????????????§??¨???
}

Point crosspoint(Line l,Line m){
    //??????l??¨??????m?????????
    if(intersectSS(l,m) == false)return Point(INF,INF);
    return m[0]+(m[1]-m[0])*cross(l[1]-l[0],l[1]-m[0])/cross(l[1]-l[0],m[1]-m[0]);
}
 
Polygon ConvexHull(Polygon v){
    //??????????????????
    int n = v.size();
    int k = 0;
    sort(v.begin(),v.end());
    Polygon e(2*n);
    for(int i=0;i<n;e[k++]=v[i++])
        while(k>=2&&ccw(e[k-2],e[k-1],v[i])<=0)k--;
    for(int i=n-2,t=k+1;i>=0;e[k++]=v[i--])
        while(k>=t&&ccw(e[k-2],e[k-1],v[i])<=0)k--;
    e.resize(k-1);
    return e;
}

struct edge
{
    int to;
    double cost;
    edge(){}
    edge(int _to,double _cost){
        to = _to;
        cost = _cost;
    }
    bool operator < (const edge &a)const{
        return a.cost<cost;
    }
};
typedef pair<Point,int> P;

int main(){
    int N;
    while(scanf("%d",&N),N){
        Circle C[128];
        vector < pair < Point , int >  > points;
        Point start,goal;
        rep(i,N){
            double x,y,r;
            scanf("%lf%lf%lf",&x,&y,&r);
            if(i == 0){
                start = Point(x,y);
            }
            if(i == N-1){
                goal = Point(x,y);
            }
            C[i] = Circle(Point(x,y),r);
        }
        vector < Line > arc;
        points.PB(P(start,0));
        rep(i,N){
            reps(j,i+1,N){
                Point p,q;
                int tmp = intersectCC(C[i],C[j],&p,&q);
                if(tmp > 0){
                    points.PB(P(p,j));
                    points.PB(P(q,j));
                    Line l;
                    l.PB(p);l.PB(q);
                    arc.PB(l);
         //         cout << p.x << " " << p.y << "\n";
         //         cout << q.x << " " << q.y << "\n";
                }
            }
        }
       // puts("$$$$$$$$$$$$$$$$$$$$$$");
        points.PB(P(goal,N-1));
        int goal_ID = points.size()-1;

        vector< edge > G[250];
        rep(i,points.size()){
            reps(j,i+1,points.size()){
                double dist = pabs(points[i].fi-points[j].fi);
                Line l;
                l.PB(points[i].fi);
                l.PB(points[j].fi);
                int cnt = 0;
                Point p,q;
                bool flg = true;
        //        cout << "&" <<points[i].se+1 << " " << points[j].se << "\n";
                for(int k = points[i].se+1; k < points[j].se+1; k++){
                    bool a = true;
                    a = intersectSS(l,arc[k-1]);
                    //cout << a << "\n";
                    if(!a){
                        flg = false;
                    }
                }
                if(!flg)continue;
                G[i].PB(edge(j,dist));
                G[j].PB(edge(i,dist));
            //    cout << i << " " << j << " " << dist << " "<< flg <<"\n";
            }
        }

        double d[250];
        fill(d,d+250,INF);
        priority_queue < edge > Q;
        Q.push(edge(0,0.0));

        while(!Q.empty()){
            edge e = Q.top();Q.pop();
            if(d[e.to] != INF)continue;
            d[e.to] = e.cost;
            rep(i,G[e.to].size()){
                Q.push(edge(G[e.to][i].to,G[e.to][i].cost+d[e.to]));
            }
        }

        printf("%.4lf\n",d[goal_ID]);
    }
    return 0;
}

Measured memory_bytes: 1440