#include<iostream>
#include<iomanip>
#include<queue>
#include<set>
#include<vector>
#include<functional>
#include<algorithm>
#define Loop(i, n) for (int i = 0; i < int(n); i++)
#define INF INFINITY
using namespace std;

const double PI = 3.14159265358979323846;
const double eps = 1e-7;
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool fge(double x, double y) { return x >= y - eps; }
double fsqrt(double x) { return feq(x, 0) ? 0 : sqrt(x); }

struct pt_t {
	double x, y;
	pt_t operator+(const pt_t &p) const { return { x + p.x, y + p.y }; }
	pt_t operator-(const pt_t &p) const { return { x - p.x, y - p.y }; }
	pt_t operator*(const double &c) const { return { x * c, y * c }; }
	bool operator<(const pt_t &another) const {
		return (x != another.x ? x < another.x : y < another.y);
	}
};

struct line_t {
	double a, b, c;
};

struct circle_t {
	double x, y, r;
};

line_t solve_line(double a, double b, pt_t p) {
	return { a, b, -a * p.x - b * p.y };
}

line_t solve_line(pt_t p, pt_t q) {
	return solve_line(q.y - p.y, -q.x + p.x, p);
}

double norm2(pt_t p) {
	return p.x * p.x + p.y * p.y;
}

double norm(pt_t p) {
	return sqrt(norm2(p));
}

double angle(pt_t p, pt_t q) {
	p = p * (1.0 / norm(p));
	q = q * (1.0 / norm(q));
	double r0 = acos(max(min(p.x * q.x + p.y * q.y, 1.0), -1.0));
	double r1 = asin(max(min(p.x * q.y - p.y * q.x, 1.0), -1.0));
	if (r1 >= 0) return r0;
	else return 2 * PI - r0;
}

double dist(line_t l, pt_t p) {
	return abs(l.a * p.x + l.b * p.y + l.c) / sqrt(l.a * l.a + l.b * l.b);
}

bool on_same_line(pt_t t, pt_t p) {
	line_t l = solve_line({ 0, 0 }, t);
	if (feq(dist(l, p), 0)) return true;
	else return false;
}

bool on_same_halfline(pt_t t, pt_t p) {
	line_t l = solve_line({ 0, 0 }, t);
	if (feq(dist(l, p), 0) && feq(angle(t, p), 0)) return true;
	else return false;
}

bool in_segment(pt_t s, pt_t t, pt_t p) {
	line_t l = solve_line(s, t);
	if (dist(l, p) < eps
		&& fge(p.x, min(s.x, t.x))
		&& fge(max(s.x, t.x), p.x)
		&& fge(p.y, min(s.y, t.y))
		&& fge(max(s.y, t.y), p.y)) return true;
	else return false;
}

pt_t cross_point(line_t l, line_t m) {
	double d = l.a * m.b - l.b * m.a;
	if (feq(d, 0)) {
		if (feq(l.a * m.c - l.c * m.a, 0)) return { INF, INF };
		else return { NAN, NAN };
	}
	else {
		double x = l.b * m.c - m.b * l.c;
		double y = l.a * m.c - m.a * l.c;
		return { x / d, y / -d };
	}
}

vector<pt_t> cross_point(circle_t f, line_t l) {
	double d = dist(l, { f.x, f.y });
	if (!fge(f.r, d)) return {};
	line_t m = solve_line(l.b, -l.a, { f.x, f.y });
	pt_t p = cross_point(l, m);
	if (feq(d, f.r)) return { p };
	else {
		pt_t u = { l.b, -l.a };
		pt_t v = u * (sqrt(pow(f.r, 2) - pow(d, 2)) / norm(u));
		return { p + v, p - v };
	}
}

vector<pt_t> cross_point(circle_t f, circle_t g) {
	line_t l = {
		-2 * f.x + 2 * g.x,
		-2 * f.y + 2 * g.y,
		(f.x * f.x + f.y * f.y - f.r * f.r) - (g.x * g.x + g.y * g.y - g.r * g.r)
	};
	return cross_point(f, l);
}


int main(void)
{
	while (1) {
		int n;
		cin >> n;
		if (!n) break;
		vector<circle_t> p(n);
		Loop(i, n) {
			cin >> p[i].x >> p[i].y >> p[i].r;
		}
		vector<pt_t> d(2 * n);
		pt_t s, e;
		d[0].x = p[0].x; d[0].y = p[0].y;
		d[2 * n - 1].x = p[n - 1].x; d[2 * n - 1].y = p[n - 1].y;

		Loop(i, n - 1) {
			vector<pt_t> get = cross_point(p[i], p[i + 1]);
			d[2 * i + 1] = get[0];
			d[2 * i + 2] = get[1];
		}
		vector<vector<double>> dis(2 * n, vector<double>(2 * n));
		Loop(i, 2 * n) {
			for (int j = i + 1; j < 2 * n; j++) {
				bool flag = 1;
				int l = (i - 1) / 2;
				if (i == 0) l = -1;
				int r = (j - 1) / 2;
				for (int k = l + 1; k < r; k++) {
					line_t get1 = solve_line(d[2 * k + 1], d[2 * k + 2]);
					line_t get2 = solve_line(d[i], d[j]);
					flag = in_segment(d[2 * k + 1], d[2 * k + 2], cross_point(get1, get2));
					if (!flag) break;
				}
				if (!flag) dis[i][j] = INF;
				else dis[i][j] = norm(d[i] - d[j]);
			}
		}
		vector<double> dp(2 * n, INF);
		vector<int> from(2 * n, -1);
		dp[0] = 0;
		for (int i = 0; i < 2 * n; i++) {
			for (int j = i + 1; j < 2 * n; j++) {
				double x = dp[i] + dis[i][j];
				if (x < dp[j]) {
					dp[j] = x;
					from[j] = i;
				}
			}
		}
		cout << setprecision(12) << dp[2 * n - 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 3376