#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>

using namespace std;
typedef pair<double, int> pdi;
const double EPS = 1e-8;
const double INF = 1e10;

struct Point {
	double x, y;
	Point() : x(0), y(0) { }
	Point(double x, double y) : x(x), y(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*(double s) const { return Point(x * s, y * s); }
	Point operator/(double s) const { return Point(x / s, y / s); }
	Point &operator+=(const Point &p){ x += p.x; y += p.y; return *this; }
	Point &operator-=(const Point &p){ x -= p.x; y -= p.y; return *this; }
	Point &operator*=(double s){ x *= s; y *= s; return *this; }
	Point &operator/=(double s){ x /= s; y /= s; return *this; }
	bool operator==(const Point &p) const { return x == p.x && y == p.y; }
	bool operator!=(const Point &p) const { return x != p.x || y != p.y; }
	bool operator<(const Point &p) const {
		return (x == p.x) ? (y < p.y) : (x < p.x);
	}
};
inline Point operator*(double s, const Point &p){ return p * s; }

inline double norm(const Point &p){ return p.x * p.x + p.y * p.y; }
inline double abs(const Point &p){ return sqrt(norm(p)); }
inline double arg(const Point &p){ return atan2(p.y, p.x); }
inline Point unit(const Point &p){ return p / abs(p); }
inline Point ortho(const Point &p){ return Point(-p.y, p.x); }
inline double cross(const Point &a, const Point &b){
	return a.x * b.y - a.y * b.x;
}
inline double dot(const Point &a, const Point &b){
	return a.x * b.x + a.y * b.y;
}
inline int ccw(const Point &a, const Point &b, const Point &c){
	const Point d = b - a, e = c - a;
	if(cross(d, e) > 0.0){ return 1; }
	if(cross(d, e) < 0.0){ return -1; }
	if(dot(d, e) < 0.0){ return 2; }
	if(abs(d) < abs(e)){ return -2; }
	return 0;
}

struct Line {
	Point a, b;
	Line() : a(), b() { }
	Line(const Point &a, const Point &b) : a(a), b(b) { }
	bool operator==(const Line &l) const { return a == l.a && b == l.b; }
	bool operator!=(const Line &l) const { return a != l.a || b != l.b; }
	bool operator<(const Line &l) const {
		return (a == l.a) ? (b < l.b) : (a < l.a);
	}
};

struct Segment : public Line {
	Segment() : Line() { }
	Segment(const Point &a, const Point &b) : Line(a, b) { }
};

inline bool intersect(const Segment &a, const Segment &b){
	if(ccw(a.a, a.b, b.a) * ccw(a.a, a.b, b.b) > 0){ return false; }
	if(ccw(b.a, b.b, a.a) * ccw(b.a, b.b, a.b) > 0){ return false; }
	return true;
}

struct Circle {
	Point p;
	double r;
	Circle() : p(), r(0) { }
	Circle(Point p, double r) : p(p), r(r) { }
	bool operator==(const Circle &c) const { return p == c.p && r == c.r; }
	bool operator!=(const Circle &c) const { return p != c.p || r != c.r; }
	bool operator<(const Circle &c) const {
		return (p == c.p) ? (r < c.r) : (p < c.p);
	}
};

inline double heron(double a, double b, double c){
	double s = (a + b + c) / 2.0;
	return sqrt(s * (s - a) * (s - b) * (s - c));
}

inline vector<Point> crossing_points(const Circle &a, const Circle &b){
	const double l = abs(b.p - a.p);
	const double d = 2.0 * heron(l, a.r, b.r) / l;
	const double t = sqrt(a.r * a.r - d * d);
	const Point v = t * unit(b.p - a.p);
	const Point w = d * unit(ortho(v));
	return vector<Point>({ a.p + v + w, a.p + v - w });
}

int main(){
	ios_base::sync_with_stdio(false);
	cout << setiosflags(ios::fixed) << setprecision(10);
	while(true){
		int n;
		cin >> n;
		if(n == 0){ break; }
		vector<Circle> circles(n);
		for(int i = 0; i < n; ++i){
			Circle &c = circles[i];
			cin >> c.p.x >> c.p.y >> c.r;
		}
		vector<Segment> segments(n + 1);
		segments[0] = Segment(circles[0].p, circles[0].p);
		for(int i = 1; i < n; ++i){
			const vector<Point> points =
				crossing_points(circles[i - 1], circles[i]);
			segments[i] = Segment(points[0], points[1]);
		}
		segments[n] = Segment(circles[n - 1].p, circles[n - 1].p);
		const int m = (n + 1) * 2;
		vector<Point> points(m);
		for(int i = 0; i <= n; ++i){
			points[i * 2 + 0] = segments[i].a;
			points[i * 2 + 1] = segments[i].b;
		}
		vector< vector<pdi> > conn(m);
		for(int i = 0; i < m; ++i){
			const int si = i / 2;
			for(int j = i + 1; j < m; ++j){
				const int sj = j / 2;
				Segment s(points[i], points[j]);
				bool accept = true;
				for(int k = si + 1; accept && k < sj; ++k){
					if(!intersect(s, segments[k])){ accept = false; }
				}
				if(!accept){ continue; }
				const double c = abs(points[i] - points[j]);
				conn[i].push_back(pdi(c, j));
				conn[j].push_back(pdi(c, i));
			}
		}
		vector<double> dist(m, INF);
		vector<int> done(m);
		priority_queue< pdi, vector<pdi>, greater<pdi> > pq;
		dist[0] = 0.0;
		pq.push(pdi(0.0, 0));
		while(!pq.empty()){
			const pdi p = pq.top();
			pq.pop();
			const double c = p.first;
			const int u = p.second;
			if(done[u]){ continue; }
			done[u] = 1;
			for(int i = 0; i < conn[u].size(); ++i){
				const double nc = c + conn[u][i].first;
				const int v = conn[u][i].second;
				if(!done[v] && nc < dist[v]){
					dist[v] = nc;
					pq.push(pdi(nc, v));
				}
			}
		}
		cout << dist.back() << endl;
	}
	return 0;
}

Measured memory_bytes: 1448