#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
#include<iomanip>
#include<queue>
#include<string>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<algorithm>
#include<functional>	//for "greater<type>"
#include<cmath>
using namespace std;
#define pb push_back
#define fi first
#define sc second
#define mp make_pair
#define is insert	//tentative

#define DEBUG 1

#define INF (1.0/0.0)
#define EPS 1e-8
#define PI 3.1415926535
#define EQ(x, y) (abs((x)-(y))<EPS)
#define GE(x, y) ((x)>(y)||EQ(x, y))
#define LE(x, y) ((x)<(y)||EQ(x, y))
//Don't change because there are many "x"s, and "y"s in other uses.
#define X real()	//for complex
#define Y imag()	//for complex

typedef complex<double> point;//changed
typedef point vec;//changed
typedef array<point, 2> line;//changed
typedef vector<point> poly;//changed

struct circle {//changed
	point c;
	double r;
};

enum geometry {ABC=-2, CW, ACB, CCW, CAB, ON_LINE, OUTSIDE, INSIDE, ERROR};//Each means collinear(order: a-b-c), clockwise, collinear, counter clockwise,collinear, etc. Remember that ERROR means 2 of the 3 points are duplicate.//changed

namespace std {
	bool operator<(point a, point b) {
		if (!EQ(a.X, b.X)) return a.X < b.X;
		if (!EQ(a.Y, b.Y)) return a.Y < b.Y;
		return false;
	}

	bool operator>(point a, point b) {
		return b<a;
	}

	bool operator<=(point a, point b) {
		return !(a>b);
	}
}

double dot(point a, point b) {
	return (conj(a)*b).X;
}

double cross(point a, point b) {
	return (conj(a)*b).Y;
}

geometry ccw(point a, point b, point c) {//changed
	a -= b;
	c -= b;
	if (cross(a, c) > EPS) return CCW;//counter clockwise
	if (cross(a, c) < -EPS) return CW;//clockwise
	if (dot(a, c) < -EPS) return ABC;//collinear (order: a - b - c)

	double al = abs(a);
	double cl = abs(c);
	//error: 2 of a, b, and c are duplicate.
	if (EQ(al, cl)) return ERROR;//At least a, and c are duplicate.
	if (EQ(min(al, cl), 0)) return ERROR;
	if (al < cl) return CAB;//collinear (order: c - a - b)
	else return ACB;//collinear (order: a - c - b)
}

point proj(line l, point p) {
	point v = l[1]-l[0];
	double ratio = dot(v, p-l[0]) / norm(v);
	return l[0] + ratio*v;
}

point refl(line l, point p) {
	return p + (proj(l, p) - p) * 2.0;
}

vec rotate(vec v, double r) {
	return v*vec(cos(r), sin(r));
}

//Get a normal vector (??????????????????).
vec Normalvec(line l){//changed (added)
	vec v=(vec)l[1]-l[0];
	return vec (v.Y,-v.X);
}

bool IsOrthogonal(line l, line m) {
	vec v1 = l[1]-l[0];
	vec v2 = m[1]-m[0];
	return EQ(dot(v1, v2), 0.0);
}

bool IsParallel(line l, line m) {
	vec v1 = l[1]-l[0];
	vec v2 = m[1]-m[0];
	return EQ(cross(v1, v2), 0.0);
}

bool IntersectLL(line l, line m) {
	if (!EQ(cross(l[1]-l[0], m[1]-m[0]), 0.0)) return true;
	if (EQ(cross(l[1]-l[0], m[0]-l[0]), 0.0)) return true;
	return false;
}

bool IntersectLS(line l, line s) {//This outputs true if l includes an endpoint of s.
	point b = l[0];
	vec v = l[1]-l[0];
	return cross(v, s[0]-b)*cross(v, s[1]-b) < EPS;
}

bool IntersectSS(line s, line t) {
	// hard coding: CW := -1, CCW := 1 -> Only CW*CW and CCW*CCW are equal to 1
	if (ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) == 1) return false;
	if (ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) == 1) return false;
	if (!IsParallel(s, t)) return true;
	if (max(s[0], s[1]) < min(t[0], t[1])) return false;
	if (max(t[0], t[1]) < min(s[0], s[1])) return false;
	return true;
}

bool IntersectLP(line l, point p) {
	return EQ(cross(l[1]-p, l[0]-p), 0.0);
}

bool IntersectSP(line s, point p) {
	return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS;
}

double DistL(line l) {
	return abs(l[0]-l[1]);
}

double DistLP(line l, point p) {
	return abs(p - proj(l, p));
}

double DistLL(line l, line m) {
	if (!IntersectLL(l, m)) return 0;
	return DistLP(l, m[0]);
}

double DistLS(line l, line s) {
	if (IntersectLS(l, s)) return 0;
	return min(DistLP(l, s[0]), DistLP(l, s[1]));
}

double DistSP(line s, point p) {
	point r = proj(s, p);
	if (IntersectSP(s, r)) return abs(r - p);
	return min(abs(s[0]-p), abs(s[1]-p));
}

double DistSS(line s, line t) {
	if (IntersectSS(s, t)) return 0;

	double a = min(DistSP(s, t[0]), DistSP(s, t[1]));
	double b = min(DistSP(t, s[0]), DistSP(t, s[1]));
	return min(a, b);
}

line PerpendBisect(line seg) {//?????´????????????
	point mid = (seg[0]+seg[1])/2.0;
	return line{mid, mid+(seg[1]-seg[0])*vec(0, 1)};
}

point CrosspointLL(line l, line m) {
	double A = cross(l[1]-l[0], m[1]-m[0]);
	double B = cross(l[1]-l[0], l[1]-m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0];
	if (abs(A) < EPS) assert(0);
	return m[0] + B / A * (m[1]-m[0]);
}

vector<point> CrosspointCL(circle c, line l) {
	vector<point> ret;
	double d = DistLP(l, c.c);
	if (EQ(d, c.r)) {
		ret.emplace_back(proj(l, c.c));
	} else if (d < c.r) {
		double ratio = sqrt(c.r*c.r - d*d);
		vec sgn = (l[0]-l[1]) / abs(l[0]-l[1]);
		ret.emplace_back(proj(l, c.c) + ratio*sgn);
		ret.emplace_back(proj(l, c.c) - ratio*sgn);
	}

	return ret;
}

vector<point> CrosspointCS(circle c, line s) {
	vector<point> ret;
	vector<point> res = CrosspointCL(c, s);
	if (s[0] > s[1]) swap(s[0], s[1]);
	for (point p : res) {
		if (s[0] <= p && p <= s[1]) ret.emplace_back(p);
	}
	return ret;
}

vector<point> CrosspointCC(circle c1, circle c2) {
	vector<point> ret;
	double d = abs(c1.c - c2.c);
	double rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
	double dfr = c1.r*c1.r - rc*rc;

	if (EQ(dfr, 0.0)) dfr = 0.0;
	else if(dfr < 0.0) return ret;

	double rs = sqrt(dfr);
	vec sgn = (c2.c - c1.c) / d;
	ret.emplace_back(c1.c + sgn*point(rc, rs));
	if (dfr > 0.0) ret.emplace_back(c1.c + sgn*point(rc, -rs));
	return ret;
}

geometry Positioningpoint(poly poly, point p) {
	bool in = false;
	int n = poly.size();
	for (int i=0; i<n; i++) {
		point a = poly[i];
		point b = poly[(i+1)%n];
		vec u = a - p;
		vec v = b - p;

		if (u.Y > v.Y) swap(u, v);

		double cr = cross(u, v);
		if (u.Y <= 0 && 0 < v.Y && cr > EPS) in ^= 1;
		if (IntersectSP({a, b}, p)) return ON_LINE;
	}

	if (in) return INSIDE;
	return OUTSIDE;
}

// Note that ccw(a, b, c) != CCW when a, b, c are colinear
poly GrahamScan(vector<point> ps) {
	if (ps.size() <= 2) return ps;

	int k = 0;
	int n = ps.size();
	poly ret(n*2);

	sort(ps.begin(), ps.end());
	for (int i=0; i<n; i++) {
		while (k > 1 && ccw(ret[k-2], ret[k-1], ps[i]) != CCW) k--;
		ret[k++] = ps[i];
	}

	int k_ = k;
	for (int i=n-1; i>=0; i--) {
		while (k > k_ && ccw(ret[k-2], ret[k-1], ps[i]) != CCW) k--;
		ret[k++] = ps[i];
	}

	ret.resize(k-1);
	return ret;
}

bool IsConvex(poly ps) {
	return GrahamScan(ps).size() == ps.size();
}

poly CapConvexes(poly pp, poly qq) {
#if DEBUG
	assert (IsConvex(pp));
	assert (IsConvex(qq));
#endif

	poly ret;
	int a = 0;
	int b = 0;
	int aa = 0;
	int bb = 0;
	int n = pp.size();
	int m = qq.size();
	enum {PIN, QIN, UNKNOWN} in = UNKNOWN;

	auto forward_a = [&](bool put) {
		if (put && in == PIN) ret.emplace_back(pp[a]);
		a = (a+1)%n;
		aa++;
	};

	auto forward_b = [&](bool put) {
		if (put && in == QIN) ret.emplace_back(qq[b]);
		b = (b+1)%m;
		bb++;
	};

	auto intersect_1pt = [](point &a, point &b, point &c, point &d, point &r) {
		double D =	cross(b - a, d - c);
		if (EQ(D, 0)) return false;
		double t =	cross(c - a, d - c) / D;
		double s = -cross(a - c, b - a) / D;
		r = a + t * (b - a);
		return GE(t, 0) && LE(t, 1) && GE(s, 0) && LE(s, 1);
	};

	do {
		int apre = (a+n-1)%n;
		int bpre = (b+m-1)%m;
		double C = cross(pp[a]-pp[apre], qq[b]-qq[bpre]);
		double A = cross(pp[apre]-qq[b], pp[a]-qq[b]);
		double B = cross(qq[bpre]-pp[a], qq[b]-pp[a]);
		point r;
		if (intersect_1pt(pp[apre], pp[a], qq[bpre], qq[b], r)) {
			if (in == UNKNOWN) aa = bb = 0;
			ret.emplace_back(r);
			if (B > 0) in = PIN;
			else if (A > 0) in = QIN;
		}

		if (EQ(A, 0) && EQ(B, 0) && EQ(C, 0)) {
			if (in == PIN) forward_b(false);
			else forward_a(false);
		} else if (C >= 0) {
			if (A > 0) forward_a(true);
			else forward_b(true);
		} else {
			if (B > 0) forward_b(true);
			else forward_a(true);
		}
	} while ((aa < n || bb < m) && aa < 2*n && bb < 2*m);

	if (in == UNKNOWN) {
		if (Positioningpoint(qq, pp[0]) != OUTSIDE) return pp;
		if (Positioningpoint(pp, qq[0]) != OUTSIDE) return qq;
	}
	return ret;
}

double CalcArea(poly ps) {
	double ret = 0.0;
	for (int i=0; i<ps.size(); i++) {
		ret += cross(ps[i], ps[(i+1)%ps.size()]);
	}
	return ret/2.0;
}

// Convex* requires the elements of ps to be arranged counter clockwise.
pair<int, int> ConvexDiameterApexes(poly ps) {
#if DEBUG
	assert (IsConvex(ps));
#endif

	int n = ps.size();
	int is = 0;
	int js = 0;
	for (int i=1; i<n; i++) {
		if (ps[i].Y > ps[is].Y) is = i;
		if (ps[i].Y < ps[js].Y) js = i;
	}

	int maxi, maxj;
	double maxd = norm(ps[is]-ps[js]);
	int i = is;
	int j = js;
	do {
		vec a = ps[i+1] - ps[i];
		vec b = ps[j+1] - ps[j];
		if (cross(a, b) > -EPS) j = (j+1)%n;
		else i = (i+1)%n;

		double d = norm(ps[i]-ps[j]);
		if (d > maxd) {
			maxd = d;
			maxi = i;
			maxj = j;
		}
	} while (i != is || j != js);

	return make_pair(maxi, maxj);
}

line ClosestPair(vector<point> ps) {
	auto CompareY = [](const point &a, const point &b) {
		if (a.Y != b.Y) return a.Y < b.Y;
		return a.X < b.X;
	};

	function<line(point*,int)> Rec = [&Rec, &CompareY](point *ps, int n) {
		if (n <= 1) return line{point(0, 0), point(INF, INF)};
		
		int m = n/2;
		double x = ps[m].X;
		line a = Rec(ps, m);
		line b = Rec(ps+m, n-m);
		double mind = DistL(a);
		line ret = a;
		if (DistL(b) < mind) {
			mind = DistL(b);
			ret = b;
		}

		sort(ps, ps+n, CompareY);
		vector<point> qs;
		qs.reserve(n);
		for (int i=0; i<n; i++) {
			if (abs(ps[i].X - x) >= mind) continue;

			for (int j=0; j<qs.size(); j++) {
				point p1 = ps[i];
				point p2 = qs[qs.size()-1-j];
				if (p1.Y - p2.Y >= mind) break;

				double d = abs(p1-p2);
				if (mind > d) {
					mind = d;
					ret = line{p1, p2};
				}
			}

			qs.emplace_back(ps[i]);
		}

		return ret;
	};

	int n = ps.size();
	assert (n >= 2);
	sort(ps.begin(), ps.end());
	return Rec(&ps[0], n);
}

// Convex* requires the elements of ps to be arranged counter clockwise.
// <left, right> or <upper, lower>
pair<poly, poly> CutConvex(poly ps, line l) {
#if DEBUG
	assert (IsConvex(ps));
#endif

	//if (l[0].Y > l[1].Y) swap(l[0], l[1]);
	//else if (EQ(l[0].Y, l[1].Y) && l[0].X > l[1].X) swap(l[0], l[1]);

	poly left;
	poly right;
	for (int i=0; i<ps.size(); i++) {
		point a = ps[i];
		point b = ps[(i+1)%ps.size()];

		if (ccw(l[0], l[1], a) != CW) left.emplace_back(a);
		else right.emplace_back(a);

		line m{a, b};
		if (IntersectLS(l, m)) {
			point p = CrosspointLL(l, m);
			left.emplace_back(p);
			right.emplace_back(p);
		}
	}

	return make_pair(left, right);
}

circle Circum(point a, point b, point c) {
	circle ret{{INF, INF}, 0.0};
	line l{a, b};
	line m{b, c};
	line lp = PerpendBisect(l);
	line mp = PerpendBisect(m);
	if (IsParallel(lp, mp)) return ret;

	ret.c = CrosspointLL(lp, mp);
	ret.r = abs(a-ret.c);
	return ret;
}

vector<point> Tangentpoints(circle c, point p) {
	vector<point> ret;
	double d = abs(c.c-p);
	if (EQ(d, c.r)) {
		ret.emplace_back(p);
		return ret;
	}

	if (d < c.r) return ret;

	vec v = (p-c.c)/d*c.r;
	double t = acos(c.r/d);
	ret.emplace_back(c.c + rotate(v, t));
	ret.emplace_back(c.c + rotate(v, -t));
	return ret;
}

vector<line> CommonTangents(circle p, circle q) {
#if DEBUG
	assert(!EQ(p.c, q.c) || !EQ(p.r, q.r));
#endif

	double pr = p.r;
	double qr = q.r;
	point pc = p.c;
	point qc = q.c;
	double d = abs(pc - qc);
	double dr = abs(pr - qr);
	double sr = abs(pr + qr);

	vector<line> ret;
	if (EQ(d, sr)) {//If the 2 circles tangent exclusively,
		point cp = (pc * qr + qc * pr) / sr;
		vec v = cp - pc;
		ret.emplace_back(line{cp, cp + v*vec(0, 1)});
	} else if (d > sr) {//If the 2 have no intersection,
		point cp = (pc * qr + qc * pr) / sr;
		vector<point> pts = Tangentpoints(p, cp);
		vector<point> qts = Tangentpoints(q, cp);
		for (int i=0; i<2; i++) {
			line l{pts[0], qts[i]};
			if(IntersectLP(l, cp)) {
				ret.emplace_back(l);
				ret.emplace_back(line{pts[1], qts[i^1]});
			}
		}
	} 

	if (EQ(d, dr)) {//If the 2 tangent inclusively,
		point cp = pc + (pc-qc) / (qr-pr) * pr;
		vec v = cp - pc;
		ret.emplace_back(line{cp, cp + v*vec(0, 1)});
	} else if (d > dr) {//If the 2 intersect,
		if (EQ(pr, qr)) {
			point v = (qc - pc) / d * pr;
			v *= point(0, 1);
			ret.emplace_back(line{pc+v, qc+v});
			ret.emplace_back(line{pc-v, qc-v});
		} else {
			point cp = pc + (qc-pc) * pr / (pr-qr);
			vector<point> pts = Tangentpoints(p, cp);
			vector<point> qts = Tangentpoints(q, cp);
			for (int i=0; i<2; i++) {
				line l{pts[0], qts[i]};
				if(IntersectLP(l, cp)) {
					ret.emplace_back(l);
					ret.emplace_back(line{pts[1], qts[i^1]});
					break;
				}
			}
		}
	} 

	return ret;
}

#define DIJKSTRA_MAX_N 200
typedef pair<double,int> pii;

struct edge{
	int to;
	double cost;
};

const double inf=1000000001;
int n;//Be careful of the number of the vertexes of g (=2*n).
double d[DIJKSTRA_MAX_N];
vector<edge> g[DIJKSTRA_MAX_N];

void dijkstra(int v){
	priority_queue<pii,vector<pii>,greater<pii> > q;
	fill(d,d+2*n,inf);
	d[v]=0;
	q.push(mp(0,v));
	while(!q.empty()){
		double D=q.top().fi;
		int w=q.top().sc;
		q.pop();
		if(D>d[w]){
			continue;
		}
		for(int j=0;j<g[w].size();++j){
			int u=g[w][j].to;
			double c=g[w][j].cost;
			if(d[u]>D+c){
				d[u]=D+c;
				q.push(mp(d[u],u));
			}
		}
	}
}

void solve(){
	circle c[100];
	vector<point> v[100];
	for(int i=0;i<n;++i){
		double x,y;
		cin>>x>>y>>c[i].r;
		c[i].c=point (x,y);
	}
	for(int i=0;i<n-1;++i){//v[i][j]: 2*i+j+1-th (0-indexed) in g.
		v[i]=CrosspointCC(c[i],c[i+1]);
	}
	for(int i=0;i<n-2;++i){
		for(int j=i+1;j<n-1;++j){
			for(int k=0;k<2;++k){
				for(int l=0;l<2;++l){
					point p=v[i][k],q=v[j][l];
					line s={p,q};
					bool f=false;
					for(int m=i;m<j;++m){
						if(!IntersectSS(s,(line){v[m][0],v[m][1]})){
							f=true;
							break;
						}
					}
					if(f){
						continue;
					}
					g[2*i+k+1].pb((edge){2*j+l+1,abs(p-q)});
				}
			}
		}
	}
	for(int j=0;j<n-1;++j){
		for(int l=0;l<2;++l){
			point p=c[0].c,q=v[j][l];
			line s={p,q};
			bool f=false;
			for(int m=0;m<j;++m){
				if(!IntersectSS(s,(line){v[m][0],v[m][1]})){
					f=true;
					break;
				}
			}
			if(f){
				continue;
			}
			g[0].pb((edge){2*j+l+1,abs(p-q)});
		}
	}
	for(int i=0;i<n-1;++i){
		for(int k=0;k<2;++k){
			point p=v[i][k],q=c[n-1].c;
			line s={p,q};
			bool f=false;
			for(int m=i;m<n-1;++m){
				if(!IntersectSS(s,(line){v[m][0],v[m][1]})){
					f=true;
					break;
				}
			}
			if(f){
				continue;
			}
			g[2*i+k+1].pb((edge){2*n-1,abs(p-q)});
		}
	}
	point p=c[0].c,q=c[n-1].c;
	line s={p,q};
	bool f=false;
	for(int m=0;m<n-1;++m){
		if(!IntersectSS(s,(line){v[m][0],v[m][1]})){
			f=true;
			break;
		}
	}
	if(!f){
		g[0].pb((edge){2*n-1,abs(p-q)});
	}
	dijkstra(0);
	cout<<fixed<<setprecision(3)<<d[2*n-1]<<endl;
	for(int i=0;i<2*n;++i){
		g[i].clear();
	}
}

int main(){
	while(true){
		cin>>n;
		if(n==0){
			break;
		}
		solve();
	}
}

Measured memory_bytes: 3444