#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
#include <cassert>
#include <complex>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

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

typedef complex<double> point;
const double EPS = 1e-9;

namespace std {
	bool operator==(const point &p, const point &q) {
		return abs(p.X - q.X) < EPS && abs(p.Y - q.Y) < EPS;
	}

	bool operator!=(const point &p, const point &q) {
		return !(p == q);
	}

	bool operator<(const point &p, const point &q) {
		return p.X + EPS < q.X || abs(p.X - q.X) < EPS && p.Y + EPS < q.Y;
	}

	bool operator>(const point &p, const point &q) {
		return q < p;
	}
}

double dot(const point &l, const point &r) {
	return real(conj(l)*r);
}

double cross(const point &l, const point &r) {
	return imag(conj(l)*r);
}

point rotate90(const point &p)
{
	return point(-p.Y, p.X);
}

point rotate(const point &p, const double theta)
{
	return polar(abs(p), arg(p)+theta);
}

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

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

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

typedef vector<point> polygon;

inline int ccw(const point& a, point b, point c) {
	b = b - a;
	c = c - a;
	const double tmp = cross(b, c);
	if(tmp > EPS) return 1; // ccw
	if(tmp < -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 順で一直線上
}

inline 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;
}

inline 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;
}

inline 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;
}

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

inline 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;
}

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

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

inline 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);
}

inline double dist(const line& l, const point& p) {
	return abs(cross((l.b - l.a), (p - l.a))) / abs(l.b - l.a);
}

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

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

inline double dist(const segment& s, const point& p) {
	if(dot((s.b - s.a), (p - s.a)) < 0) return abs(p - s.a);
	if(dot((s.a - s.b), (p - s.b)) < 0) return abs(p - s.b);
	return dist(line(s.a, s.b), p);
}

inline 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)));
}

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

inline bool intersect(const circle& c, const segment& s) {
	return dist(s, c.c) < c.r + EPS;
}

inline 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 m.a + (m.b - m.a) * cross(l.b - l.a, l.a - m.a) * (1.0 / tmp);
}

inline 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 t.a + (t.b - t.a) * cross(s.b - s.a, s.b - t.a) * (1.0 / tmp);
}

//先に，intersectを用いて交差判定を行うこと
inline 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;
}

inline 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;
}

inline 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;
}

inline double areaTriangle(point a, point b, const point& c) {
	a = a - c;
	b = b - c;
	return fabs(a.X * b.Y - b.X * a.Y) / 2.0;
}

inline double area(const polygon& p) {
	const int num = p.size();
	if(num < 3)
		return 0;

	if(num == 3)
		return areaTriangle(p[0], p[1], p[2]);

	double res = cross(p[num - 1], p[0]);
	for(int i = 1; i < num; ++i)
		res += cross(p[i - 1], p[i]);

	return abs(res) * 0.5;
}

// L.aからL.bの方向を見た場合に，点aが左側に来る．
inline line bisector(const point& a, const point& b) {
	return line(point((a.X - a.Y + b.X + b.Y) / 2.0, (a.Y + a.X + b.Y - b.X) / 2.0),
				point((a.X + a.Y + b.X - b.Y) / 2.0, (a.Y - a.X + b.Y + b.X) / 2.0));
}

// 点集合 pointsの凸包を求める．
inline polygon convex_hull(vector<point> points) {
	const int n = points.size();
	if(n <= 3)
		return points;

	sort(points.begin(), points.end());
	int k = 0;
	polygon res;
	res.resize(2 * n);
	for(int i = 0; i < n; res[k++] = points[i++])
		while(k >= 2 && ccw(res[k - 2], res[k - 1], points[i]) <= 0)
			--k;

	const int t = k + 1;
	for(int i = n - 2; i >= 0; res[k++] = points[i--])
		while(k >= t && ccw(res[k - 2], res[k - 1], points[i]) <= 0)
			--k;

	res.resize(k - 1);
	return res;
}
// L.aからL.bを向いた時の左側を残して切断する．
inline polygon convex_cut(const polygon& p, const line& l) {
	const int num = p.size();
	polygon res;
	for(int i = 0; i < num; ++i) {
		const int next = (i + 1) % num;
		const int tmp = ccw(l.a, l.b, p[i]);
		if(tmp != -1)
			res.push_back(p[i]);

		if(tmp * ccw(l.a, l.b, p[next]) < 0)
			res.push_back(crosspoint(l, line(p[i], p[next])));
	}

	return res;
}

vector<point> tangent(const circle& c, const point& p) {
	const double x = norm(p - c.c);
	double d = x - c.r * c.r;
	if(d < -EPS) return vector<point>();
	d = max(d, 0.0);
	const point q1 = (p - c.c) * (c.r * c.r / x);
	const point q2 = rotate90((p - c.c) * (-c.r * sqrt(d) / x));
	vector<point> res;
	res.push_back(c.c + q1 - q2);
	res.push_back(c.c + q1 + q2);
	return res;
}

vector<line> tangent(const circle &a, const circle& b) {
	vector<line> res;
	if(abs(a.r - b.r) < EPS) {
		point dir = b.c - a.c;
		dir = rotate90(dir * (a.r / abs(dir)));
		res.push_back(line(a.c + dir, b.c + dir));
		res.push_back(line(a.c - dir, b.c - dir));
	}
	else {
		point p = a.c * (-b.r) + b.c * a.r;
		p = p * (1.0 / (a.r - b.r));
		vector<point> ps = tangent(a, p), qs = tangent(b, p);
		for(int i = 0; i < min<int>(ps.size(), qs.size()); ++i)
			res.push_back(line(ps[i], qs[i]));
	}

	point p = a.c * b.r + b.c * a.r;
	p = p * (1.0 / (a.r + b.r));
	vector<point> ps = tangent(a, p), qs = tangent(b, p);
	for(int i = 0; i < min<int>(ps.size(), qs.size()); ++i)
		res.push_back(line(ps[i], qs[i]));

	return res;
}

// 三角形と点の包含関係，境界は含まない．
// 含める場合は == -1を <= 0とする．
bool contain_triangle(const polygon& triangle, const point& p) {
	const int d1 = ccw(p, triangle[0], triangle[1]), d2 = ccw(p, triangle[1], triangle[2]), d3 = ccw(p, triangle[2], triangle[0]);
	return !(d1 * d2 == -1 || d2 * d3 == -1 || d3 * d1 == -1);
}

// 多角形と点の包含関係．境界を含む．
bool contain(const polygon& P, const point& p) {
	const int n = P.size();
	bool res = false;
	for(int i = 0; i < n; ++i) {
		point v1 = P[i] - p, v2 = P[(i + 1) % n] - p;
		if(v1.Y > v2.Y)
			swap(v1, v2);

		if(v1.Y < EPS && EPS < v2.Y && cross(v1, v2) > EPS)
			res = !res;

		if(abs(cross(v1, v2)) < EPS && dot(v1, v2) < EPS)
			return true; // 境界を含まないなら，falseにする．
	}

	return res;
}

int n;
int start, goal;

struct edge{
	int to;
	double cost;
};

const double INF = 1e100;
const int MAX = 300;
vector<edge> G[MAX];

typedef pair<double, int> pdi;
double d[MAX];
bool connect[MAX][MAX];

class node {
public:
	int v;
	node() {}
	node(int v):v(v) {}

	bool operator<(const node &r) const {
		return d[v] > d[r.v];
	}
};

vector< pair<point, pii> > ps;

double dijkstra()
{
	fill(d, d+MAX, INF);
	priority_queue<node> que;

	d[start] = 0;
	que.push(node(start));
	while (!que.empty()) {
		node n = que.top(); que.pop();
		if (n.v == goal)
			break;
		rep(i, G[n.v].size()) {
			edge e = G[n.v][i];
			double c = d[n.v] + e.cost;
			if (d[e.to] > c) {
				d[e.to] = c;
				que.push(node(e.to));
			}
		}
	}

	return d[goal];
}

int main()
{
	while (cin >> n, n) {
		vector<circle> cs;
		ps.clear();

		rep(i, n) {
			int x, y, r;
			cin >> x >> y >> r;
			cs.push_back(circle(point(x, y), r));
		}

		ps.push_back(make_pair(cs[0].c, pii(0, 0)));
		for (int i = 1; i < cs.size(); i++) {
			if (intersect(cs[i-1], cs[i])) {
				vector<point> buf = crosspoint(cs[i-1], cs[i]);
				rep (j, 2)
					ps.push_back(make_pair(buf[j], pii(i-1, i)));
			}
		}
		{
			int t = cs.size()-1;
			ps.push_back(make_pair(cs[t].c, pii(t, t)));
		}

		int sz = ps.size();
		rep(i, sz) {
			REP(j, i+1, sz) {
				int lb = ps[i].second.second;
				int ub = ps[j].second.first;
				bool f = true;
				segment s = segment(ps[i].first, ps[j].first);
				for (int k = lb+1; k <= ub; k++) {
					vector<point> buf = crosspoint(cs[k-1], cs[k]);
					segment t = segment(buf[0], buf[1]);
					if (!intersect(s, t))
						f = false;
				}
				connect[i][j] = f;
				connect[j][i] = f;
			}
		}

		rep(i, sz) {
			vector<edge> e;
			rep(j, sz) {
				if (j == i) continue;
				if (connect[i][j]) {
					double d = dist(ps[i].first, ps[j].first);
					e.push_back( (edge){ j, d } );
				}
			}
			G[i] = e;
		}

		start = 0;
		goal = sz-1;
		printf("%.20lf\n", dijkstra());
	}
	return 0;
}

Measured memory_bytes: 1480