#include <iostream>
#include <vector>
#include <iomanip>
#include <complex>
#include <queue>
#include <functional>
using namespace std;

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
	bool operator < (const P& a, const P& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}
double cross(const P& a, const P& b) {
	return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
	return real(conj(a)*b);
}

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

typedef vector<P> G;

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

int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if(cross(b, c) > 0)   return +1;       // counter clockwise
	if(cross(b, c) < 0)   return -1;       // clockwise
	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;
}

bool intersectLL(const L &l, const L &m) {
	return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // non-parallel
		abs(cross(l[1] - l[0], m[0] - l[0])) < EPS;   // same line
}
bool intersectLS(const L &l, const L &s) {
	return cross(l[1] - l[0], s[0] - l[0])*       // s[0] is left of l
		cross(l[1] - l[0], s[1] - l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const L &l, const P &p) {
	return abs(cross(l[1] - p, l[0] - p)) < EPS;
}
bool intersectSS(const L &s, const L &t) {
	return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
		ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}
bool intersectSP(const L &s, const P &p) {
	return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; // triangle inequality
}

typedef double W;

struct edge {
	int to;
	W cost;
};
typedef pair<W, int> State;
typedef vector<vector <edge > > Graph;

void dijkstra(int s, const Graph G, vector<W>& d, vector<int>& prev) {
	priority_queue< State, vector<State>, greater<State> > que;
	fill(d.begin(), d.end(), INF);
	fill(prev.begin(), prev.end(), -1);

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

double x[100], y[100], r[100];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	while(cin >> n, n) {
		for(int i = 0; i < n; i++) {
			cin >> x[i] >> y[i] >> r[i];
		}

		Graph G(2 * n);
		vector<P> c;
		for(int i = 0; i < n - 1; i++) {
			double r1 = r[i], r2 = r[i + 1];
			P p1(x[i], y[i]), p2(x[i + 1], y[i + 1]);
			P v = p2 - p1;
			double t = (r1 * r1 + norm(v) - r2 * r2) / (2 * abs(v));
			double theta = acos(t / r1);
			P b1 = p1 + v / abs(v) * r1 * polar(1.0, theta);
			P b2 = p1 + v / abs(v) * r1 * polar(1.0, -theta);
			c.push_back(b1);
			c.push_back(b2);
		}

		for(int i = 0; i < c.size(); i++) {
			for(int j = i + 1; j < c.size(); j++) {
				int n1 = i / 2, n2 = j / 2;
				if(n1 == n2) continue;

				L line(c[i], c[j]);
				bool flag = true;
				for(int k = n1 + 1; k <= n2 - 1; k++) {
					if(!intersectSS(line, L(c[2 * k], c[2 * k + 1]))) {
						flag = false;
						break;
					}
				}
				if(flag) {
					double cost = abs(c[i] - c[j]);
					G[i].push_back(edge{ j, cost });
					G[j].push_back(edge{ i, cost });
				}
			}
		}

		int start = 2 * n - 2, goal = 2 * n - 1;
		c.push_back(P(x[0], y[0]));
		c.push_back(P(x[n - 1], y[n - 1]));
		for(int i = 0; i < start; i++) {
			int n1 = i / 2;
			L line(c[i], c[start]);
			bool flag = true;
			for(int k = 0; k <= n1 - 1; k++) {
				if(!intersectSS(line, L(c[2 * k], c[2 * k + 1]))) {
					flag = false;
					break;
				}
			}
			if(flag) {
				double cost = abs(c[i] - c[start]);
				G[start].push_back(edge{ i, cost });
				G[i].push_back(edge{ start, cost });
			}
		}
		for(int i = 0; i < start; i++) {
			int n1 = i / 2;
			L line(c[i], c[goal]);
			bool flag = true;
			for(int k = n1 + 1; k < n - 1; k++) {
				if(!intersectSS(line, L(c[2 * k], c[2 * k + 1]))) {
					flag = false;
					break;
				}
			}
			if(flag) {
				double cost = abs(c[i] - c[goal]);
				G[i].push_back(edge{ goal, cost });
				G[goal].push_back(edge{ i, cost });
			}
		}

		L line(c[start], c[goal]);
		bool flag = true;
		for(int k = 0; k <= n - 1; k++) {
			if(!intersectSS(line, L(c[2 * k], c[2 * k + 1]))) {
				flag = false;
				break;
			}
		}
		if(flag) {
			double cost = abs(c[start] - c[goal]);
			G[start].push_back(edge{ goal, cost });
		}

		vector<W> d(2 * n);
		vector<int> prev(2 * n);
		dijkstra(start, G, d, prev);
		cout << setprecision(15) << d[goal] << endl;
	}
}

Measured memory_bytes: 3780