#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <sstream>
  
using namespace std;
  
#define EPS 1e-9
 
struct point{
    double x, y;
    point(){x = 0;y = 0;}
    point(double a, double b) : x(a), y(b) {}
};
  
double dis(point p1,point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
 
int ccw(point p1, point p2, point p3) {
    double ret = (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
    if(abs(ret)<EPS) return 0;
    return ret > 0 ? 1 : -1;
}
 
struct Line {
	point p1,p2;
	double A,B,C;
    double getDis() {
        return dis(p1,p2);
    }
    Line() {}
    Line(double xx1, double yy1, double xx2, double yy2) {
		p1 = point(xx1,yy1), p2 = point(xx2,yy2);
		A = p1.y-p2.y, B = p2.x-p1.x, C = -(A*p1.x+B*p1.y);
	}
	Line(point t1, point t2) {
		p1 = t1, p2 = t2;
		A = p1.y-p2.y, B = p2.x-p1.x, C = -(A*p1.x+B*p1.y);
	}
};
  
bool is_in_line_seg(double x, double y, Line LL) {
    if(!( min(LL.p1.x,LL.p2.x)-EPS <= x && x <= max(LL.p1.x,LL.p2.x)+EPS 
        && min(LL.p1.y,LL.p2.y)-EPS <= y && y <= max(LL.p1.y,LL.p2.y)+EPS))
        return false;
    return abs( LL.A*x + LL.B*y + LL.C ) < EPS;
}

bool intersection_line_line(Line L1, Line L2, point &p) {
	double det = L1.A*L2.B - L2.A*L1.B;
	if(abs(det) < EPS) return 0;
	p.x = -(L2.B*L1.C - L1.B*L2.C) / det;
	p.y = -(L1.A*L2.C - L2.A*L1.C) / det;
	return 1;
}

bool is_cross_line_seg(Line L1, Line L2) {
	point p;
	if(!intersection_line_line(L1,L2,p)) return 0;
	return is_in_line_seg(p.x,p.y,L1) && is_in_line_seg(p.x,p.y,L2);
}
  
point intersection(point &u1,point &u2,point &v1,point &v2){
    point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
    /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}
  
void intersection_line_circle(point c, double r,point &l1,point &l2,point& p1,point&p2){
    point p=c;
    double t;
    p.x+=l1.y-l2.y;
    p.y+=l2.x-l1.x;
    p=intersection(p,c,l1,l2);
    t=sqrt(r*r-dis(p,c)*dis(p,c))/dis(l1,l2);
    p1.x=p.x+(l2.x-l1.x)*t;
    p1.y=p.y+(l2.y-l1.y)*t;
    p2.x=p.x-(l2.x-l1.x)*t;
    p2.y=p.y-(l2.y-l1.y)*t;
}
  
void intersection_circle_circle(point c1, double r1,point c2,double r2,point& p1, point& p2){
    point u,v;
    double t;
    t=(1+(r1*r1-r2*r2)/dis(c1,c2)/dis(c1,c2))/2;
    u.x=c1.x+(c2.x-c1.x)*t;
    u.y=c1.y+(c2.y-c1.y)*t;
    v.x=u.x+c1.y-c2.y;
    v.y=u.y-c1.x+c2.x;
    intersection_line_circle(c1,r1,u,v,p1,p2);
}

point P[111],cP[111][2];
int X[111],Y[111],R[111],n;
double dp[111][2];
Line LL[111];
 
int main() {
#ifdef LOCAL
	freopen("input.txt","r",stdin);
#endif

    while(1) {
        for(int i=0;i<111;++i) dp[i][0] = 1e20, dp[i][1] = 1e20;
        scanf("%d",&n);
        if(n==0) break;
        for(int i=0;i<n;++i) scanf("%d%d%d",X+i,Y+i,R+i), P[i] = point(X[i],Y[i]);
        cP[0][0] = P[0], cP[0][1] = P[0];
        cP[n][0] = P[n-1], cP[n][1] = P[n-1];
        for(int i=0;i<n-1;++i) {
            intersection_circle_circle(P[i],R[i],P[i+1],R[i+1],cP[i+1][0],cP[i+1][1]);
            LL[i+1] = Line(cP[i+1][0],cP[i+1][1]);
        }
 
        dp[0][0] = dp[0][1] = 0;
        for(int i=1;i<=n;++i) for(int ai=0;ai<2;++ai) {
            for(int j=0;j<i;++j) for(int aj=0;aj<2;++aj) {
                bool can = 1;
                Line line = Line(cP[i][ai],cP[j][aj]);
                for(int k=j+1;k<i;++k) {
                    if(!is_cross_line_seg(line,LL[k])) {can = 0; break;}
                }
 
                if(can) dp[i][ai] = min(dp[i][ai], dp[j][aj] + line.getDis());
            }
        } printf("%.10lf\n",dp[n][0]);
    }
}

Measured memory_bytes: 1236