#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) {}
} P[111],cP[111][2];
 
double dis(point p1,point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

struct Line {
	double x1,y1,x2,y2;
	double Dis() {
		return dis(point(x1,y1),point(x2,y2));
	}
	Line() {}
	Line(double a1, double b1, double a2, double b2) : x1(a1), y1(b1), x2(a2), y2(b2) {}
	Line(point p1, point p2) {
		x1 = p1.x, y1 = p1.y;
		x2 = p2.x, y2 = p2.y;
	}
	point point1() {return point(x1,y1);}
	point point2() {return point(x2,y2);}
};

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;
}
 
bool isIn(double x, double y, Line LL) {
    if(!( min(LL.x1,LL.x2)-EPS <= x && x <= max(LL.x1,LL.x2)+EPS 
        && min(LL.y1,LL.y2)-EPS <= y && y <= max(LL.y1,LL.y2)+EPS))
        return false;
    return abs( (LL.y1-y) * (LL.x2-x) - (LL.y2-y) * (LL.x1-x) ) < EPS;
}
 
bool isCross(Line L1, Line L2) {
    if(abs(L1.x1-L2.x1)<EPS && abs(L1.y1-L2.y1)<EPS
        || abs(L1.x2-L2.x2)<EPS && abs(L1.y2-L2.y2)<EPS        || abs(L1.x1-L2.x2)<EPS && abs(L1.y1-L2.y2)<EPS        || abs(L1.x2-L2.x1)<EPS && abs(L1.y2-L2.y1)<EPS)
        return true;
 
    if(isIn(L1.x1,L1.y1,L2) || isIn(L1.x2,L1.y2,L2))
        return true;
    if(isIn(L2.x1,L2.y1,L1) || isIn(L2.x2,L2.y2,L1))
        return true;
 
    int ccw1, ccw2;
 
    ccw1=ccw(L1.point1(),L1.point2(),L2.point1());
    ccw2=ccw(L1.point1(),L1.point2(),L2.point2());
 
    if(ccw1 * ccw2 >= 0) return false;
 
    ccw1=ccw(L2.point1(),L2.point2(),L1.point1());
    ccw2=ccw(L2.point1(),L2.point2(),L1.point2());
 
    if(ccw1 * ccw2 >= 0) return false;
 
    return true;
}
 
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);
}

int X[111],Y[111],R[111],n;
double dp[111][2];
Line LL[111];

int main() {
//	freopen("output.txt","w",stdout);
	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(!isCross(line,LL[k])) {can = 0; break;}
				}

				if(can) dp[i][ai] = min(dp[i][ai], dp[j][aj] + line.Dis());
			}
		} printf("%.10lf\n",dp[n][0]);
	}
}

Measured memory_bytes: 1236