#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define lengthof(array) (sizeof(array) / sizeof(*array))
#define dump(a) (cerr << (#a) << " = " << (a) << endl)
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin(); it!=(c).end();++it)
#define RFOR(it,c) for(__typeof((c).rbegin())it=(c).rbegin(); it!=(c).rend();++it)

template<class T> inline void chmax(T& a, T b) { if(b > a) a = b; }
template<class T> inline void chmin(T& a, T b) { if(b < a) a = b; }

template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << '(' << p.first << ", " << p.second << ')';
	return os;
}

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	copy(v.begin(), v.end(), ostream_iterator<T>(os, " "));
	return os;
}

const double EPS = 1e-9;
struct point {
	double x, y;
	point():x(0), y(0) {}
	point(double x, double y):x(x), y(y) {}
	point(const point& p):x(p.x), y(p.y) {}

	point operator+ (const point& p) const {
		return point(x + p.x, y + p.y);
	}

	point operator- (const point& p) const {
		return point(x - p.x, y - p.y);
	}

	point operator* (const double s) const {
		return point(x * s, y * s);
	}

	point operator* (const point& p) const {
		return point(x * p.x - y * p.y, x * p.y + y * p.x);
	}

	point operator/ (const double s) const {
		return point(x / s, y / s);
	}

	bool operator< (const point& p) const {
		return x + EPS < p.x || abs(x - p.x) < EPS && y + EPS < p.y;
	}

	bool operator== (const point& p) const {
		return abs(x - p.x) < EPS && abs(y - p.y) < EPS;
	}
};

point rotate90(const point& p) {
	return point(-p.y, p.x);
}

point rotate(const point& p, const double theta) {
	const double s = sin(theta), c = cos(theta);
	return point(c * p.x - s * p.y, s * p.x + c * p.y);
}

double angle(const point& p) {
	return atan2(p.y, p.x);
}

double abs(const point& p) {
	return sqrt(p.x * p.x + p.y * p.y);
}

double norm(const point& p) {
	return p.x * p.x + p.y * p.y;
}

double dot(const point& l, const point& r) {
	return l.x * r.x + l.y * r.y;
}

double cross(const point& l, const point& r) {
	return l.x * r.y - l.y * r.x;
}

struct line {
	point a, b;
	line(point a, point b):a(a), b(b){}
};

struct segment {
	point a, b;
	segment(point a, point b):a(a), b(b){}
};

struct circle {
	point c;
	double r;
	circle():c(point(0, 0)), r(0.0){}
	circle(point c, double r):c(c), r(r){}
};

typedef vector<point> polygon;

int ccw(const point& a, point b, point c) {
	b = b - a;
	c = c - a;
	if(cross(b, c) > EPS) return 1; // ccw
	if(cross(b, c) < -EPS) return -1; // cw
	if(dot(b, c) < 0) return 2; // c, a, b 順に一直線上
	if(norm(b) < norm(c)) return -2; // a, b, c 順に一直線上
	return 0; //a, c, b 順で一直線上
}

point projection(const line& l, const point& p) {
	const point dif = l.b - l.a;
	const double tmp = dot(p - l.a, dif) / norm(dif);
	return l.a + dif * tmp;
}

bool intersect(const line& l, const line& m) {
	return abs(cross(l.b - l.a, m.b - m.a)) > EPS || abs(cross(l.b - l.a, m.b - l.a)) < EPS;
}

bool intersect(const line& l, const segment& s) {
	return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS;
}

bool intersect(const line& l, const point& p) {
	return abs(ccw(l.a, l.b, p)) != -1;
}

bool intersect(const segment& s, const segment& t) {
	return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
		ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

bool intersect(const segment& s, const point& p) {
	return ccw(s.a, s.b, p) == 0;
}

bool intersect(const circle& c, const point& p) {
	return abs(c.c - p) <= c.r + EPS;
}

bool intersect(const circle& c, const circle& d) {
	return abs(c.c - d.c) <= c.r + d.r && abs(c.c - d.c) >= abs(c.r - d.r);
}

double dist(const point& a, const point& b) {
	return abs(a - b);
}

double dist(const line& l, const point& p) {
	return abs(p - projection(l, p));
}

double dist(const line& l, const line& m) {
	return intersect(l, m) ? 0 : dist(l, m.a);
}

double dist(const line& l, const segment& s) {
	return intersect(l, s) ? 0 : min(dist(l, s.a), dist(l, s.b));
}

double dist(const segment& s, const point& p) {
	const point tmp = projection(line(s.a, s.b), p);
	return intersect(s, tmp) ? abs(tmp - p) : min(abs(s.a - p), abs(s.b - p));
}

double dist(const segment& s, const segment& t) {
	if(intersect(s, t))
		return 0;
	return min(min(dist(s, t.a), dist(s, t.b)), min(dist(t, s.a), dist(t, s.b)));
}

point crosspoint(const line& l, const line& m) {
	const double tmp = cross(l.b - l.a, m.b - m.a);
	if(abs(tmp) < EPS) // 平行
		return l.a;
	return l.a + (l.b - l.a) * cross(m.b - m.a, m.b - l.a) * (1.0 / tmp);
}

point crosspoint(const segment& s, const segment& t) {
	if(!intersect(s, t)) // 交点を持たない
		return s.a; // 用改善

	const double tmp = cross(s.b - s.a, t.b - t.a);
	if(abs(tmp) < EPS) { // 一直線上
		if(intersect(s, t.a)) return t.a;
		if(intersect(s, t.b)) return t.b;
		if(intersect(t, s.a)) return s.a;
		return s.b;
	}

	return s.a + (s.b - s.a) * cross(s.b - s.a, s.b - t.a) * (1.0 / tmp);
}

vector<point> crosspoint(const circle &c, const circle& d) {
	vector<point> res;
	if(abs(c.c - d.c) < EPS) // 中心の座標が同じ
		return res;

	const double tmp = abs(c.c - d.c);
	const double rc = (tmp * tmp + c.r * c.r - d.r * d.r) / (tmp + tmp);
	const double rs = sqrt(c.r * c.r - rc * rc);
	const point diff = (d.c - c.c) / tmp;
	res.push_back(point(c.c + diff * point(rc, rs)));
	res.push_back(point(c.c + diff * point(rc, -rs)));
	return res;
}

vector<point> crosspoint(const circle& c, const line& l) {
	vector<point> res;
	const point h = projection(l, c.c);
	const double d = abs(h - c.c);
	if(d > c.r - EPS) {
		res.push_back(h);
	}
	else if(d <= c.r - EPS) {
		point v = l.b - l.a;
		v = v * sqrt(c.r * c.r - d * d) / abs(v);
		res.push_back(h + v);
		res.push_back(h - v);
	}

	return res;
}

vector<point> crosspoint(const circle& c, const segment& s) {
	vector<point> res;
	vector<point> tmp = crosspoint(c, line(s.a, s.b));
	for(int i = 0; i < tmp.size(); ++i)
		if(intersect(s, tmp[i]))
			res.push_back(tmp[i]);

	return res;
}

double area(const polygon& p) {
	double res = 0.0;
	const int num = p.size();
	for(int i = 0; i < num; ++i) {
		res += cross(p[i], p[(i + 1) % num]);
	}

	return res * 0.5;
}

vector<circle> circles;
vector<vector<point> > c_p;

struct edge {
	int to;
	double cost;
	edge(int t, double c):to(t), cost(c){}
};
typedef pair<int, int> P;

vector<vector<edge> > es;

double dijkstra(int s, int t) {
	priority_queue<P, vector<P>, greater<P> > que;
	vector<double> d(es.size(), INT_MAX);
	que.push(P(0, s));
	d[s] = 0;
	
	while(!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if(d[v] < p.first)
			continue;

		if(v == t)
			return d[t];

		for(int i = 0; i < es[v].size(); ++i) {
			edge& e = es[v][i];
			if(d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}

	return -1;
}

inline bool in_range(const segment& s, const point& p, const point& q) {
	int tmp = ccw(s.a, s.b, p) * ccw(s.a, s.b, q);
	return tmp == -1 || tmp == 0;
}

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

	for(int n; scanf("%d", &n), n;) {
		circles.clear();
		circles.resize(n);
		for(int i = 0; i < n; ++i) {
			int x, y, r;
			scanf("%d %d %d", &x, &y, &r);
			circles[i] = circle(point(x, y), r);
		}

		c_p.clear();
		c_p.resize(n - 1, vector<point>(2));
		for(int i = 0; i < n - 1; ++i) {
			vector<point> tmp = crosspoint(circles[i], circles[i + 1]);
			c_p[i][0] = tmp[0];
			c_p[i][1] = tmp[1];
		}

		es.clear();
		es.resize(2 * n + 2);

		for(int i = 0; i < n - 1; ++i)
			for(int j = 0; j <= 1; ++j)
				for(int k = i + 1; k < n - 1; ++k)
					for(int l = 0; l <= 1; ++l) {
						const segment s(c_p[i][j], c_p[k][l]);
						for(int m = i + 1; m < k; ++m)
							if(!in_range(s, c_p[m][0], c_p[m][1]))
								goto ng;

						es[i + j * n].push_back(edge(k + l * n, dist(s.a, s.b)));
					ng:;
					}


		for(int i = 0; i < n - 1; ++i)
			for(int j = 0; j <= 1; ++j) {
				const segment s(circles[0].c, c_p[i][j]);
				for(int m = 0; m < i; ++m)
					if(!in_range(s, c_p[m][0], c_p[m][1]))
						goto ng2;

				es[2 * n].push_back(edge(i + j * n, dist(s.a, s.b)));
			ng2:;
			}


		for(int i = 0; i < n - 1; ++i)
			for(int j = 0; j <= 1; ++j) {
				const segment s(c_p[i][j], circles[n - 1].c);
				for(int m = i + 1; m < n - 1; ++m) {
					if(!in_range(s, c_p[m][0], c_p[m][1]))
						goto ng3;
				}
				es[i + j * n].push_back(edge(2 * n + 1, dist(s.a, s.b)));
			ng3:;
			}

		{
			const segment s(circles[0].c, circles[n - 1].c);
			for(int i = 0; i < n - 1; ++i) {
				if(!in_range(s, c_p[i][0], c_p[i][1]))
					goto ng4;
			}
			es[2 * n].push_back(edge(2 * n + 1, dist(s.a, s.b)));
		ng4:;
		}

		printf("%.10lf\n", dijkstra(2 * n, 2 * n + 1));
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1348