#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef complex<double> pt;
#define pu push
#define pb push_back
#define mp make_pair
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
const double EPS = 1e-9;
#define x real()
#define y imag()
int n;
pt za[105];
double r[105];
vector<pt> CCintersect (pair<pt,double> c, pair<pt,double> d) {
    vector<pt> ret;
    double dist = abs(c.first - d.first);
    double cr = c.second;
    double dr = d.second;
     
    if (dist > cr + dr) return ret;
    if (dist < abs(cr - dr)) return ret;
     
    double s = (cr + dr + dist) / 2.;
    double area = sqrt(s * (s - cr) * (s - dr) * (s - dist));
    double h = 2 * area / dist;
     
    pt v = d.first - c.first; v /= abs(v);
    pt m = c.first + sqrt(cr * cr - h * h) * v;
    pt n = v * pt(0, 1);
     
    ret.push_back(m + n * h);
    ret.push_back(m - n * h);
    return ret;
}
bool eq(double a,double b){
  return (-EPS < a-b && b-a < EPS);
}
double dot(pt a,pt b){
	return (conj(a)*b).x;
}
double cross(pt a,pt b){
	return (conj(a)*b).y;
}
double dist_lp(pt a,pt b,pt c){
	//senbun a-b to c no dist
	if(dot(a-b,c-b) <= 0.0) return abs(c-b);
	if(dot(b-a,c-a) <= 0.0) return abs(c-a);
	return abs(cross(b-a,c-a)) / abs(b-a);
}
int ccw(pt a,pt b,pt c){
	b -= a; c -= a;
	if(cross(b,c) > EPS) return 1; // counter clockwise
	if(cross(b,c) < -EPS) return -1; // clockwise
	if(dot(b,c) < -EPS) return 2; //c-a-b
	if(norm(b) < norm(c)) return -2; //a-b-c
	return 0; //a-c-b
}

bool intersect(pt a,pt b,pt c,pt d){
	return (ccw(a,b,c)*ccw(a,b,d) <= 0 && ccw(c,d,a)*ccw(c,d,b) <= 0);
}
int main(){
	while(1){
		cin >> n; if(!n) return 0;
		for(int i=1;i<=n;i++){
			scanf("%lf%lf%lf",&za[i].x,&za[i].y,&r[i]);
		}
		vector<pt>v; v.pb(za[1]);
		for(int i=1;i<n;i++){
			vector<pt>R = CCintersect(mp(za[i],r[i]),mp(za[i+1],r[i+1]));
			v.pb(R[0]); v.pb(R[1]);
		}
		v.pb(za[n]);
		bool ok[205][205]={};
		for(int i=0;i<v.size();i++){
			for(int j=i+1;j<v.size();j++){
				int I,J;
				if(i==0) I = 1;
				else I = (i+1)/2+1;
				if(j==v.size()-1) J = n-1;
				else J = (j-1)/2;
				if(I>J) ok[i][j] = true;
				else{
					for(int k=I;k<=J;k++){
						vector<pt>R = CCintersect(mp(za[k],r[k]),mp(za[k+1],r[k+1]));
						if(!intersect(R[0],R[1],v[i],v[j])) goto bad;
					}
					ok[i][j] = true; bad:;
				}
			}
		}
		double dist[205];
		for(int i=0;i<205;i++){
			dist[i] = 1e9;
		}
		dist[0] = 0.0;
		priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >que;
		que.push(mp(0.0,0));
		while(!que.empty()){
			pair<double,int> di = que.top(); que.pop();
			if(!eq(dist[di.sc],di.fi)) continue;
			for(int i=0;i<v.size();i++){
				if(!ok[di.sc][i]) continue;
				if(dist[di.sc]+abs(v[i]-v[di.sc])+EPS < dist[i]){
					dist[i] = dist[di.sc]+abs(v[i]-v[di.sc]);
					que.push(mp(dist[i],i));
				}
			}
		}
		printf("%.6f\n",dist[v.size()-1]);
	}
}

Measured memory_bytes: 3344