#include<bits/stdc++.h>
using namespace std;

#define IL inline 
namespace geo {
	typedef double D;
	typedef bool B;
	struct P {
		D X, Y;
		B operator<(const P &o)const { return (X == o.X) ? Y < o.Y : X < o.X; }
		P operator+ (P o) { return P{ X + o.X,Y + o.Y }; }
		P operator- (P o) { return P{ X - o.X,Y - o.Y }; }
		P operator* (D o) { return P{ X*o,Y*o }; }
		P operator/ (D o) { return P{ X/o,Y/o }; }
		P operator-() { return P{ -X,-Y }; }
	};
	typedef tuple<P, P> L;  //line
	typedef tuple<P, P> LS; //line segment
	typedef tuple<P, D> C;  //circle
	typedef vector<P> Poly;
	const D EPS = 1e-8;
	IL P iMUL(P p, P q) {return P{ p.X*q.X - p.Y*q.Y,p.X*q.Y + p.Y*q.X };}

	IL D ABS(P p) { return sqrt(p.X*p.X + p.Y*p.Y); }
	//A dot B
	IL D dot(P a, P b) { return a.X*b.X + a.Y*b.Y; }
	//A cross B
	IL D cross(P a, P b) { return a.X*b.Y - a.Y*b.X; }

	IL D signed_distance_P_L(P p, L l) {
		P a, b, c = p;
		tie(a, b) = l;
		return cross(b - a, c - a) / ABS(b - a);
	}

	IL D distance_P_L(P p, L l) {
		return abs(signed_distance_P_L(p,l));
	}

	IL D distance_P_LS(P p, LS ls) {
		P a, b, c = p;
		tie(a, b) = ls;
		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);
	}

	IL B isintersected_L_L(L p, L q) {
		P a, b, c, d;
		tie(a, b) = p;
		tie(c, d) = q;
		return (abs(cross(a - b, c - d)) > EPS);
	}
	IL B isintersected_L_LS(L l, LS 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));
	}
	IL B isintersected_LS_LS(LS p, LS 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
	IL P cross_point_L_L(L p, L q) {
		P a, b;
		tie(a, b) = p;
		D d1 = signed_distance_P_L(a, q);
		D d2 = signed_distance_P_L(b, q);
		return (a * d2 - b * d1) / (d2 - d1);
	}

	IL B isintersected_C_C(C p, C q) {
		P cp, cq;
		D rp, rq;
		tie(cp, rp) = p;
		tie(cq, rq) = q;
		D d = ABS(cp - cq);
		return abs(rp - rq) < d + EPS&&d < rp + rq + EPS;
	}
	IL LS cross_C_C(C p, C q) {
		P cp, cq;
		D rp, rq;
		tie(cp, rp) = p;
		tie(cq, rq) = q;
		D d = ABS(cp - cq);
		D rc = (d*d + rp*rp - rq*rq) / (2 * d);
		D rs = sqrt(rp*rp - rc*rc);
		P diff = (cq - cp) / d;
		return LS(cp + iMUL(P{ rc, rs },diff), cp + iMUL(P{ rc, -rs },diff));
	}

}



#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<C> c(n);
		range(it, c) {
			double x, y, r;
			cin >> x >> y >> r;
			it = C(P{ x, y }, r);
		}

		vector<LS> ls;
		{
			P s, g;
			{
				double t;
				tie(s, t) = c[0];
				tie(g, t) = c[n - 1];
			}
			ls.push_back(LS(s, s));
			rep(i, n - 1)ls.push_back(cross_C_C(c[i], c[i + 1]));
			ls.push_back(LS(g, g));
		}
		
		vector<vector<double>> DP(n + 1, vector<double>(2, INF));
		DP[0][0] = DP[0][1] = 0;
		for (int i = 1; i < n + 1; i++) {
			for (int j = 0; j < i; j++) {
				vector<P> v = { get<0>(ls[i]),get<1>(ls[i]) };
				vector<P> u = { get<0>(ls[j]),get<1>(ls[j]) };
				rep(a,2)rep(b,2){
					auto s = LS(v[a], u[b]);
					bool flag = true;
					for (int k = j + 1; k < i; k++)flag &= (isintersected_LS_LS(s, ls[k]));
					if (flag)DP[i][a] = min(DP[i][a], DP[j][b] + ABS(v[a]-u[b]));
				}

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


	}
	return 0;
}

Measured memory_bytes: 3256