/*
* Problem link
* 
*/

#include<bits/stdc++.h>
using namespace std;
#include<vector>
#include<algorithm>
#include<complex>
#include<map>
#include<math.h>
using namespace std;
namespace geo {

	typedef complex<double> P;
	typedef vector<P> Poly;
	const double eps = 1e-8;
	typedef tuple<P, P> Line;
	typedef tuple<P, double> Circle;
#define mp(a,b) make_pair(a,b)

	inline void x(P& p, double n) { p.real(n); }
	inline void y(P& p, double n) { p.imag(n); }
	inline double x(P& p) { return p.real(); }
	inline double y(P& p) { return p.imag(); }

	inline double dot(const P a, const  P b) {//A dot B
		return a.real()*b.real() + a.imag()*b.imag();
	}

	inline double cross(const P a, const P b) {//A cross B
		return a.real()*b.imag() - a.imag()*b.real();
	}


	inline double distance_line(P p, Line l) {
		auto c = p;
		P a, b;
		tie(a, b) = l;
		return abs(cross(b - a, c - a)) / abs(b - a);
	}
	inline double signed_distance_line(P p, Line l) {
		auto c = p;
		P a, b;
		tie(a, b) = l;
		return cross(b - a, c - a) / abs(b - a);
	}
	inline double distance_line_segment(P p, Line l) {
		P a, b;
		tie(a, b) = l;
		auto c = p;
		if (dot(b - a, c - a) < eps) return abs(c - a);
		if (dot(a - b, c - b) < eps) return abs(c - b);
		return abs(cross(b - a, c - a)) / abs(b - a);
	}

	inline bool isintersected_L_L(Line p, Line q) {
		P a, b, c, d;
		tie(a, b) = p;
		tie(c, d) = q;
		return (abs(cross(a - b, c -d))>eps);
	}
	inline bool isintersected_L_LS(Line l, Line ls) {
		P a, b, c, d;
		tie(a, b) = l;
		tie(c, d) = ls;
		return !((cross(a - b, b - a) > -eps) ^ (cross(a - b, d - a) < eps));
	}
	inline bool isintersected_LS_LS(Line p, Line q) {
		P a, b, c, d;
		tie(a, b) = p;
		tie(c, d) = q;
		return cross(b - a, c - a)*cross(b - a, d - a) < eps&&cross(d - c, a - c)*cross(d - c, b - c) < eps;
	}
	//caution: have to use isintersected_L_L before this function
	inline P cross_point_L_L(Line p, Line q) {
		P a, b;
		tie(a, b) = p;
		auto d1 = signed_distance_line(a, q);
		auto d2 = signed_distance_line(b, q);
		cout << d1 << " " << d2 << endl;
		return (a * d2 - b * d1) / (d2 - d1);
	}


	int comp(const P &l, const P &r) {
		if (l.real() == r.real())
			return(l.imag() < r.imag());
		return(l.real() < r.real());
	}

	inline bool isintersected_C_C(Circle p, Circle q){
		P cp, cq;
		double rp, rq;
		tie(cp, rp) = p;
		tie(cq, rq) = q;
		auto d = abs(cp - cq);
		return abs(rp - rq) < d + eps&&d < rp + rq + eps;
	}
	inline Line cross_C_C(Circle p, Circle q) {
		P cp, cq;
		double rp, rq;
		tie(cp, rp) = p;
		tie(cq, rq) = q;
		auto d = abs(cp - cq);
		auto rc = (d*d + rp*rp - rq*rq) / (2 * d);
		auto rs = sqrt(rp*rp - rc*rc);
		auto diff = (cq - cp) / d;
		return Line(cp + diff*P(rc, rs), cp + diff*P(rc, -rs));
	}
}
#define rep(i,N) for(auto i=(N)*0;i<N;i++)
#define range(it,v) for(auto &it:v)
struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;
using namespace geo;
const double INF = 1e9;
int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cout << setprecision(10);
	cout << fixed;
	int n;
	while (cin >> n, n) {
		vector<Circle> C(n);
		range(it, C) {
			double x, y, r;
			cin >> x >> y >> r;
			it = Circle(P(x, y), r);
		}
		P s, g; 
		{
			double t;
			tie(s, t) = C[0];
			tie(g, t) = C[n - 1];
		}
	
		vector<Line> L;
		L.push_back(Line(s, s));
		rep(i, n-1) 
			L.push_back(cross_C_C(C[i], C[i + 1]));
		L.push_back(Line(g, g));
		vector<vector<double>> DP(n+1, vector<double>(2, INF));
		DP[0][0] = 0;
		DP[0][1] = 0;
		for (int i = 1; i < n + 1;i++) {
			P p, q;
			tie(p, q) = L[i];
			for (int j = 0; j < i; j++) {
				P u, v;
				tie(u, v) = L[j];
				{
					auto ls = Line(u, p);
					bool flag = true;
					for (int k = j + 1; k < i; k++)flag &= (isintersected_LS_LS(ls, L[k]));
					if (flag)DP[i][0] = min(DP[i][0],DP[j][0]+abs(p - u));
				}
				{
					auto ls = Line(v, p);
					bool flag = true;
					for (int k = j + 1; k < i; k++)flag &= (isintersected_LS_LS(ls, L[k]));
					if (flag)DP[i][0] = min(DP[i][0], DP[j][1] + abs(p - v));
				}

				{
					auto ls = Line(u, q);
					bool flag = true;
					for (int k = j + 1; k < i; k++)flag &= (isintersected_LS_LS(ls, L[k]));
					if (flag)DP[i][1] = min(DP[i][1], DP[j][0] + abs(q - u));
				}

				{
					auto ls = Line(v, q);
					bool flag = true;
					for (int k = j + 1; k < i; k++)flag &= (isintersected_LS_LS(ls, L[k]));
					if (flag)DP[i][1] = min(DP[i][1], DP[j][1] + abs(q - v));
				}

			}
		}
		cout << min(DP[n][0], DP[n][1]) << endl;

		
	}
	return 0;
}

Measured memory_bytes: 3348