#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <complex>
#include <cassert>
#include <cmath>
#include <cstdio>

using namespace std;

const double EPS = 1e-8;
const double INF = 1e12;

typedef complex<double> P;

#define X real()
#define Y imag()

#define Curr(P, i) P[(i)%P.size()]
#define Next(P, i) P[(i+1)%P.size()]
#define Prev(P, i) P[(i+P.size()-1)%P.size()]

namespace std{
	bool operator<(const P a, const P b) {
		return a.X != b.X ? a.X < b.X : a.Y < b.Y;
	}
}

double cross(const P a, const P b) {
	return (conj(a)*b).imag();
}
double dot(const P a, const P b) {
	return (conj(a)*b).real();
}

int ccw(P a, P b, P c) {
	b -= a;
	c -= a;
	if (cross(b, c) > 0) return +1;
	if (cross(b, c) < 0) return -1;
	if (dot(b, c) < 0) return +2;
	if (norm(b) < norm(c)) return -2;
	return 0;
}

struct L : public vector<P> {
	L(const P a, const P b) {
		push_back(a), push_back(b);
	}
};

typedef L S;
typedef vector<P> G;

struct C {
	P p;	
	double r;
	C(const P p, double r): p(p), r(r){}
};

P projection(L a, P p) {
	double t = dot(p-a[0], a[0]-a[1])/norm(a[0]-a[1]);
	return a[0] + t*(a[0]-a[1]);
}

P reflection(L a, P p) {
	return p + 2.0 * (projection(a, p)-p);
}

bool isCrossLL(L a, L b) {
	return abs(cross(a[1]-a[0], b[1]-b[0])) > EPS 
		|| abs(cross(a[1]-a[0], b[0]-a[0])) < EPS;
}

bool isCrossLS(L a, S b) {
	return cross(a[1]-a[0], b[0]-a[0])
		 * cross(a[1]-a[0], b[1]-a[0]) < EPS;
}

bool isCrossLP(L l, P p) {
	return abs(cross(l[1]-p, l[0]-p)) < EPS;
}

bool isCrossSS(S a, S b) {
	return ccw(a[0], a[1], b[0])
		 * ccw(a[0], a[1], b[1]) <= 0
		 &&
		   ccw(b[0], b[1], a[0])
		 * ccw(b[0], b[1], a[1]) <= 0;
}

bool isCrossSP(S a, P p) {
	return abs(a[0]-p)+abs(a[1]-p)-abs(a[0]-a[1]) < EPS;
}

double distPP(P a, P b) {
	return abs(a-b);
}

double distLP(L a, P p) {
	return abs(p-projection(a, p));
}

double distLL(L a, L b) {
	return isCrossLL(a, b) ? 0 : distLP(a, b[0]);
}

double distLS(L a, S b) {
	return isCrossLS(a, b) ? 0 : min(distLP(a, b[0]), distLP(a, b[1]));
}

double distSP(S a, P p) {
	const P r = projection(a, p);
	return isCrossSP(a, r) ? abs(p-r) : min(abs(a[0]-p), abs(a[1]-p));
}

double distSS(S a, S b) {
	return isCrossSS(a, b) ? 0 :
		min(
		     min(distSP(a, b[0]), distSP(a, b[1])),
			 min(distSP(b, a[0]), distSP(b, a[1]))
	    );
}

bool isCrossCP(C a, P p) {
	return abs(a.p-p)-a.r <= EPS;
}

bool isCrossCL(C a, L l) {
	return distLP(l, a.p)-a.r < EPS;
}

double distSP_MAX(S a, P p) {
	return max(abs(a[0]-p), abs(a[1]-p));
}

bool isCrossCS(C a, S s) {
	return distSP(s, a.p)-a.r<-EPS&&distSP_MAX(s, a.p)-a.r>+EPS;
}

bool isCrossCC(C a, C b) {
	return abs(a.p-b.p)-(a.r+b.r) <= EPS;
}

P crossP_LL(L a, L b) {
	double A = cross(a[1]-a[0], b[1]-b[0]);
	double B = cross(a[1]-a[0], a[1]-b[0]);
	if (abs(A) < EPS && abs(B) < EPS) return b[0];
	if (abs(A) < EPS) assert(false);
	return b[0]+B/A*(b[1]-b[0]);
}

vector<P> crossP_CL(C c, L l) {
	P tmp = projection(l, c.p);
	P e = (l[0]-l[1])/abs(l[0]-l[1]);
	double h = abs(c.p-tmp)*abs(c.p-tmp);
	double t = sqrt(c.r*c.r-h*h);
	vector<P> p;
	if (t < EPS) {
		p.push_back(tmp);
		return p;
	}
	p.push_back(tmp+e*t);
	p.push_back(tmp-e*t);
	return p;
}

vector<P> crossP_CC(C a, C b) {
	double dx = (b.p).X-(a.p).X;
	double dy = (b.p).Y-(a.p).Y;
	double A = dx * dx + dy * dy;
	double B = ((a.r * a.r - b.r * b.r) / A + 1) / 2;
	double D = a.r * a.r / A - B * B;
	D = sqrt(D);
	double x3 = (a.p).X + dx * B;
	double y3 = (a.p).Y + dy * B;
	double x4 = -dy * D;
	double y4 = dx * D;
	vector<P> p;
	p.push_back(P(x3-x4, y3-y4));
	p.push_back(P(x3+x4, y3+y4));
	return p;
}

typedef pair<double, int> R;

int V;

struct edge {
	int to;
	double cost;
};

vector<edge> GG[200];
double d[200];

void dijkstra(int s) {
	priority_queue<R, vector<R>, greater<R> > que;
	fill(d, d+V, INF);
	d[s] = 0;
	que.push(R(0.0, s));

	while (!que.empty()) {
		R p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < GG[v].size(); i++) {
			edge e = GG[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(R(d[e.to], e.to));
			}
		}
	}
}

int main() {
	int n;

	while (cin >> n) {
		if (n == 0) {
			break;
		}
		for (int i = 0; i < 200; i++) {
			GG[i].clear();
		}
		vector<C> en;
		vector<P> ten;
		for (int i = 0; i < n; i++) {
			double a, b, c;
			cin >> a >> b >> c;
			C k = C(P(a, b), c);
			en.push_back(k);
		}
		ten.push_back(en[0].p);
		for (int i = 1; i < n; i++) {
			vector<P> p = crossP_CC(en[i-1], en[i]);
			ten.push_back(p[0]);
			ten.push_back(p[1]);
		}
		ten.push_back(en[n-1].p);
		for (int i = 1; i < 2*n; i++) {
			for (int j = 0; j < i; j++) {
				int t;
				if (j % 2 == 0) {
					t = j+1;
				} else {
					t = j+2;
				}
				bool hantei = true;
				for (int k = t; k < i; k += 2) {
					if (!isCrossSS(S(ten[k], ten[k+1]), S(ten[i], ten[j]))) {
						hantei = false;
						break;
					}
				}
				if (hantei) {
					edge e = {j, distPP(ten[i], ten[j])};
					GG[i].push_back(e);
					e.to = i;
					GG[j].push_back(e);
				}
			}
		}
		V = 2*n;
		dijkstra(0);
		printf("%f\n", d[2*n-1]);
	}
	return 0;
}

Measured memory_bytes: 1480