#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;

#include<complex>
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8, pi = acos(-1.0);
ld dot(Point a, Point b) { return real(conj(a)*b); }
ld cross(Point a, Point b) { return imag(conj(a)*b); }
namespace std {
	bool operator<(const Point &lhs, const Point &rhs) {
		return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real();
	}
}
struct Line {
	Point a, b;
};
struct Circle {
	Point p; ld r;
};
int ccw(Point a, Point b, Point c) {
	b -= a; c -= a;
	if (cross(b, c) > eps)return 1;//counter clockwise
	if (cross(b, c) < -eps)return -1;//clock wise
	if (dot(b, c) < 0)return 2;//c--a--b on line
	if (norm(b) < norm(c))return -2;//a--b--c on line
	return 0; //a--c--b on line
}

vector<Point> is_cc(Circle c1, Circle c2) {
	vector<Point> res;
	ld d = abs(c1.p - c2.p);
	ld rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2 * d);
	ld dfr = c1.r*c1.r - rc * rc;
	if (abs(dfr) < eps)dfr = 0.0;
	if (dfr < 0.0)return res;
	ld rs = sqrt(dfr);
	Point diff = (c2.p - c1.p) / d;
	res.push_back(c1.p + diff * Point(rc, rs));
	if (dfr != 0.0)res.push_back(c1.p + diff * Point(rc, -rs));
	return res;
}
Point proj(Line l, Point p) {
	ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
	return l.a + t * (l.a - l.b);
}
bool isis_ss(Line s, Line t) {
	return(cross(s.b - s.a, t.a - s.a)*cross(s.b - s.a, t.b - s.a) < -eps && cross(t.b - t.a, s.a - t.a)*cross(t.b - t.a, s.b - t.a) < -eps);
}
ld dist_lp(Line l, Point p) {
	return abs(p - proj(l, p));
}
vector<Point> is_lc(Circle c, Line l) {
	vector<Point> res;
	ld d = dist_lp(l, c.p);
	if (d > c.r + eps)return res;
	ld len = (d > c.r) ? 0.0 : sqrt(c.r*c.r - d * d);
	Point nor = (l.a - l.b) / abs(l.a - l.b);
	res.push_back(proj(l, c.p) + len * nor);
	res.push_back(proj(l, c.p) - len * nor);
	return res;
}
vector<Point> is_sc(Circle c, Line s) {
	vector<Point> res, cop; cop = is_lc(c, s);
	int len = cop.size();
	rep(k, len) {
		if (ccw(s.a, cop[k], s.b) == -2) {
			res.push_back(cop[k]);
		}
	}
	return res;
}

struct edge {
	int to; ld cost;
};
typedef pair<ld, int> speP;

int n;

void solve() {
	vector<Circle> c(n);
	vector<Line> a(n-1);
	rep(i, n) {
		ld x, y, r; cin >> x >> y >> r;
		c[i] = { {x,y},r };
	}
	vector<vector<Point>> v(n-1);
	rep(i, n - 1) {
		v[i].resize(2);
		vector<Point> p=is_cc(c[i], c[i + 1]);
		rep(j, 2)v[i][j] = p[j];
		a[i] = { v[i][0],v[i][1] };
	}
	vector<vector<edge>> G(2*n);
	rep(i, n - 1) {
		Rep(j,i+1, n - 1) {
			rep(k1, 2) {
				rep(k2, 2) {
					Point le = v[i][k1],ri=v[j][k2];
					Line l = { le,ri };
					bool f = true;
					Rep1(k, i + 1, j - 1) {
						if (!isis_ss(l, a[k])) {
							f = false; break;
						}
					}
					if (f) {
						ld dis = abs(ri - le);
						//cout << 2 * i + k1 << " " << 2 * j + k2 << " " << le << " " << ri << " " << dis << endl;
						G[2 * i + k1].push_back({2*j+k2,dis});
					}
				}
			}
		}
	}
	rep(i, n - 1) {
		Point le = c[0].p;
		rep(j, 2) {
			Point ri = v[i][j];
			Line l = { le,ri };
			bool f = true;
			rep(k, i) {
				if (!isis_ss(l, a[k])) {
					f = false; break;
				}
			}
			if (f) {
				ld dis = abs(ri - le);

				//cout << 2 * n-2 << " " << 2 * i+j << " " << le << " " << ri << " " << dis << endl;
				G[2 * n - 2].push_back({ 2 * i + j,dis });
			}
		}
	}
	rep(i, n - 1) {
		Point ri = c[n-1].p;
		rep(j, 2) {
			Point le = v[i][j];
			Line l = { le,ri };
			bool f = true;
			Rep(k, i+1,n-1) {
				if (!isis_ss(l, a[k])) {
					f = false; break;
				}
			}
			if (f) {
				ld dis = abs(ri - le);
				//cout << 2 * i + j << " " << 2 * n-1 << " " << le << " " << ri << " " << dis << endl;
				G[2 * i+j].push_back({ 2 * n-1,dis });
			}
		}
	}
	{
		Point le = c[0].p, ri = c[n - 1].p;
		Line l = { le,ri };
		bool f = true;
		rep(k, n - 1) {
			if (!isis_ss(l, a[k])) {
				f = false; break;
			}
		}
		if (f) {
			ld dis = abs(ri - le);
			G[2 * n - 2].push_back({ 2 * n - 1,dis });
		}

	}

	vector<ld> dist(2 * n, mod);
	dist[2*n-2] = 0;
	priority_queue<speP, vector<speP>, greater<speP>> q;
	q.push({ 0,2 * n - 2 });
	while (!q.empty()) {
		speP p = q.top(); q.pop();
		int id = p.second;
		if (p.first > dist[id])continue;
		rep(j, G[id].size()) {
			int to = G[id][j].to;
			ld nd = G[id][j].cost + p.first;
			if (nd < dist[to]) {
				dist[to] = nd;
				q.push({ nd,to });
			}
		}
	}
	/*rep(i, 2 * n) {
		cout << i << " " << dist[i] << endl;
	}*/
	cout << dist[2 * n - 1] << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(9);
	//init();
	while (cin >> n,n)solve();
	//solve();
	//stop
	return 0;
}



Measured memory_bytes: 3448