#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	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 a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

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

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};
typedef Point Vector;

struct Circle{
	Point center;
	double r;
};

struct Info{
	Info(int arg_node_id,double arg_sum_dist){
		node_id = arg_node_id;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct Info &arg) const{
		return sum_dist > arg.sum_dist;
	}

	int node_id;
	double sum_dist;
};

int N;
Circle circle[100];
Point point[300];
vector<int> G[300];
double min_dist[300],dist[300][300];

double arg(Vector p){
	return atan2(p.y,p.x);
}

Vector polar(double a,double r){
	return Point(cos(r)*a,sin(r)*a);
}

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

double calc_dist(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int func(double x1,double y1,double x2, double y2, double xp, double yp){
	double naiseki,norm1,norm2,gaiseki;
	norm1 = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	norm2 = sqrt((xp-x1)*(xp-x1)+(yp-y1)*(yp-y1));
	naiseki = (xp-x1)*(x2-x1)+(yp-y1)*(y2-y1);
	gaiseki = (x2-x1)*(yp-y1)-(xp-x1)*(y2-y1);
	if(gaiseki > EPS){
		return 1;
	}else if(gaiseki < -EPS){
		return -1;
	}
	if(naiseki < -EPS){
		return 2;
	}

	if(norm1 < norm2){
		return -2;
	}
	return 0;
}


vector<Point> getCrossPoints(Circle c1,Circle c2){

	vector<Point> res;

	double d = abs(c1.center-c2.center);
	double a = acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	double t = arg(c2.center-c1.center);

	res.push_back(Point(c1.center+polar(c1.r,t+a)));
	res.push_back(Point(c1.center+polar(c1.r,t-a)));

	return res;
}

void solve(){

	for(int i = 0; i < 300; i++)G[i].clear();

	for(int i = 0; i < N; i++){
		scanf("%lf %lf %lf",&circle[i].center.x,&circle[i].center.y,&circle[i].r);
	}

	int start = 0,goal,index = 1;

	point[0] = circle[0].center;
	vector<Point> res;

	for(int i = 0; i <= N-2; i++){
		res = getCrossPoints(circle[i],circle[i+1]);
		point[index++] = res[0];
		point[index++] = res[1];
		point[index++] = circle[i+1].center;
	}

	goal = index-1;

	for(int i = 0; i < index; i++){
		for(int k = 0; k < index; k++){
			dist[i][k] = calc_dist(point[i],point[k]);
		}
	}

	bool FLG;
	int first_up,last_up;

	for(int i = 0; i < index-1; i++){
		switch(i%3){
		case 0:
			first_up = i+1;
			break;
		case 1:
			first_up = i+3;
			break;
		case 2:
			first_up = i+2;
			break;
		}

		for(int k = i+1; k < index; k++){
			FLG = true;

			switch(k%3){
			case 0:
				last_up = k-2;
				break;
			case 1:
				last_up = k-3;
				break;
			case 2:
				last_up = k-4;
				break;
			}

			for(int p = first_up; p <= last_up; p += 3){
				if(func(point[i].x,point[i].y,point[k].x,point[k].y,point[p].x,point[p].y)
						*func(point[i].x,point[i].y,point[k].x,point[k].y,point[p+1].x,point[p+1].y) > 0 ||
						func(point[p].x,point[p].y,point[p+1].x,point[p+1].y,point[i].x,point[i].y)
						* func(point[p].x,point[p].y,point[p+1].x,point[p+1].y,point[k].x,point[k].y) > 0){
					FLG = false;
					break;
				}
			}

			if(FLG){
				G[i].push_back(k);
			}
		}
	}

	for(int i = 0; i < index; i++)min_dist[i] = 999999999999.0;

	priority_queue<Info> Q;
	min_dist[start] = 0;
	Q.push(Info(start,0));

	while(!Q.empty()){

		if(Q.top().node_id == goal){
			printf("%.10lf\n",Q.top().sum_dist);
			return;
		}else if(Q.top().sum_dist > min_dist[Q.top().node_id]){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				if(min_dist[G[Q.top().node_id][i]] > Q.top().sum_dist+dist[Q.top().node_id][G[Q.top().node_id][i]]){
					min_dist[G[Q.top().node_id][i]] = Q.top().sum_dist+dist[Q.top().node_id][G[Q.top().node_id][i]];
					Q.push(Info(G[Q.top().node_id][i],min_dist[G[Q.top().node_id][i]]));
				}
			}
			Q.pop();
		}
	}
}

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		solve();
	}

	return 0;
}



Measured memory_bytes: 4408