#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
	double x, y;

	Point(double x=0, double y=0) : x(x), y(y) {}

	Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

	Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

	Point operator*(const double m) const { return Point(x*m, y*m); }

	Point operator/(const double d) const { return Point(x/d, y/d); }

	bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

	bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

	double cross(const Point &o) const { return x * o.y - y * o.x; }

	double dot(const Point &o) const { return x * o.x + y * o.y; }

	double atan() const { return atan2(y, x); }

	double norm() const { return sqrt(dot(*this)); }

	double distance(const Point &o) const { return (o - (*this)).norm(); }

	double area(const Point &a,const Point &b) {
		Point p = a - (*this), p2 = b - (*this); 
		return p.cross(p2);
	}

	double area_abs(const Point &a,const Point &b) const {
		Point p = a - (*this), p2 = b - (*this);
		return fabs(p.cross(p2)) / 2.0;
	}	

	//線分abが自身に含まれているのかどうか判断する
	int between(const Point &a,const Point &b) {
		if(area(a,b) != 0) return 0;

		if(a.x != b.x)  return ((a.x <= x) && (x <= b.x)) || ((a.x >= x) && (x >= b.x));
		else return ((a.y <= y) && (y <= b.y)) || ((a.y >= y) && (y >= b.y));
	}      

	double distance_seg(const Point& a,const Point& b) {
		if((b-a).dot(*this-a) < EPS) {
			return (*this-a).norm();
		}
		if((a-b).dot(*this-b) < EPS) {
			return (*this-b).norm();
		}
		return abs((b-a).cross(*this-a)) / (b-a).norm();
	}

	bool hitPolygon(const Point& a,const Point& b,const Point& c) {
		double t = (b-a).cross(*this-b);
		double t2 = (c-b).cross(*this-c);
		double t3 = (a-c).cross(*this-a);	

		if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
			return true;
		}

		return false;
	}
};

istream &operator >> (istream &is, Point &p) {
	return is >> p.x >> p.y;
}

ostream &operator << (ostream &out, const Point &p) {
	cout << "(" << p.x << "," << p.y << ")";
	return out;
}

struct Seg {
	Point a,b;

	Seg (Point a, Point b) : a(a),b(b) {}

	bool isOrthogonal(Seg &s) { return equals((b - a).dot(s.b - s.a),0.0); }

	bool isParallel(Seg &s) { return equals((b-a).cross(s.b - s.a),0.0); }

	bool isIntersect(Seg &s) {
		if(s.a.between(a,b) || s.b.between(a,b) || a.between(s.a,s.b) || b.between(s.a,s.b)) {
			return true;
		}
		return ((a-b).cross(s.a-a) * (a-b).cross(s.b-a) < EPS) && ((s.b-s.a).cross(a-s.a)*(s.b-s.a).cross(b-s.a) < EPS);
	}

	bool distance(Seg &s) {
		if((*this).isIntersect(s)) return 0.0;

		return min(min(a.distance_seg(s.a,s.b),b.distance_seg(s.a,s.b)),min(s.a.distance_seg(a,b),s.b.distance_seg(a,b)));
	}

	Point getCrossPoint(Seg &s) {
		Point p = s.b - s.a;
		double d = abs(p.cross(a-s.a));
		double d2 = abs(p.cross(b-s.a));

		double t = d / (d+d2);
		return a + (b-a)*t;
	}

	Point project(Point &p) {
		Point base = b - a;
		double t = base.dot(p-a) / base.dot(base);
		return a + base * t;
	}

	Point reflect(Point &p) {
		return p + (project(p) - p) * 2.0;
	}
};

struct Circle {
	Point p;
	double r;

	Circle() : p(Point(0,0)), r(0) {}

	Circle(Point o, double r) : p(o), r(r) {}

	Circle(double x,double y, double r) : p(Point(x,y)), r(r) {}

	bool isCircleIn(const Point& o) {
		Point res = o-p;
		return res.dot(res) < r*r + EPS;
	}

	// 1:外で接する，0:交差なし，-1:内で接する，2:交差，-2:内包
	int isIntersect(const Circle& c) {
		double d = (c.p - p).dot(c.p - p);
		double len = (c.r + r) * (c.r + r);

		if(equals(d,len)) return 1;
		if(d > len) return 0;

		double R = fabs(c.r - r) * fabs(c.r - r);
		if(equals(d,R)) return -1;
		if(d > R) return 2;
		return -2;
	}

	vector<Point> getCrossPoint(const Circle& c) {
		vector<Point> ret;
		int ch = isIntersect(c);

		if(ch == 0 || ch == -2) return ret;

		Point base = c.p - p;
		double len = base.dot(base);
		double t = (r*r - c.r*c.r + len) / (2.0 * len);

		if(ch == 2) {
			Point n(-base.y,base.x);
			n = n / (n.norm());
			double h = sqrt(r * r - t*t*len);

			ret.push_back(p + (base*t) + (n*h));
			ret.push_back(p + (base*t) - (n*h));
		} else {
			ret.push_back(p + (base*t));
		}

		return ret;
	}
};

struct edge {
	int from,to;
	double cost;

	edge(int t,double c) : to(t),cost(c) {}
	edge(int f,int t,double c) : from(f),to(t),cost(c) {}

	bool operator<(const edge &e) const {
		return cost < e.cost;
	}
};

vector<edge> G[100 * 100 + 5];
double d[100 * 100 + 5];

void dijkstra(int s,int n) {
	priority_queue<P,vector<P>,greater<P> > que;
	fill(d,d+n,INF);

	d[s] = 0;
	que.push(P(0,s));

	while(que.size()) {
		P p = que.top();
		que.pop();

		int v = p.second;
		if(d[v] < p.first) continue;

		rep(i,G[v].size()) {
			edge e = G[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));
			}
		}
	}
}

int main() {
	int n;

	while(cin >> n && n) {
		rep(i, 100 * 100 + 5) {
			G[i].clear();
		}

		vector<Circle> v(n);
		rep(i, n) {
			cin >> v[i].p >> v[i].r;
		}

		vector<Seg> seg;
		rep(i, n - 1) {
			vector<Point> ret = v[i].getCrossPoint(v[i+1]);
			seg.push_back(Seg(ret[0], ret[1]));
		}

		rep(i, n-1) {
			Seg s1(v[0].p, seg[i].a);
			int id = (i+1) * 2;
			bool flag = true;

			rep(j, i) {
				if(s1.isIntersect(seg[j])) continue;
				flag = false;
			}

			if(flag) {
				double dist = v[0].p.distance(s1.b);
				G[0].push_back(edge(id-1, dist));
				G[id-1].push_back(edge(0, dist));
			}

			Seg s2(v[0].p, seg[i].b);
			flag = true;
			rep(j, i) {
				if(s2.isIntersect(seg[j])) continue;
				flag = false;
			}
			
			if(flag) {
				double dist = v[0].p.distance(s2.b);
				G[0].push_back(edge(id, dist));
				G[id].push_back(edge(0, dist));
			}
		}

		rep(i, n-1) {
			bool flag = true;
			int id = (i+1) * 2;

			REP(j, i+1, n-1) {
				Seg sj1(seg[i].a, seg[j].a);
				int nid = (j+1) * 2;
				flag = true;
				REP(k, i+1, j) {
					if(sj1.isIntersect(seg[k])) continue;
					flag = false;
				}
		
				if(flag) {
					double dist = seg[i].a.distance(seg[j].a);
					G[id-1].push_back(edge(nid-1, dist));
					G[nid-1].push_back(edge(id-1, dist));
				}
		
				Seg sj2(seg[i].a, seg[j].b);
				flag = true;
				REP(k, i+1, j) {
					if(sj2.isIntersect(seg[k])) continue;
					flag = false;
				}
		
				if(flag) {
					double dist = seg[i].a.distance(seg[j].b);
					G[id-1].push_back(edge(nid, dist));
					G[nid].push_back(edge(id-1, dist));
				}
		
				Seg sj3(seg[i].b, seg[j].a);
				flag = true;
				REP(k, i+1, j) {
					if(sj3.isIntersect(seg[k])) continue;
					flag = false;
				}
		
				if(flag) {
					double dist = seg[i].b.distance(seg[j].a);
					G[id].push_back(edge(nid-1, dist));
					G[nid-1].push_back(edge(id, dist));
				}
		
				Seg sj4(seg[i].b, seg[j].b);
				flag = true;
				REP(k, i+1, j) {
					if(sj4.isIntersect(seg[k])) continue;
					flag = false;
				}
		
				if(flag) {
					double dist = seg[i].b.distance(seg[j].b);
					G[id].push_back(edge(nid, dist));
					G[nid].push_back(edge(id, dist));
				}
			}
		
		}

		rep(i, n-1) {
			Seg s3(seg[i].a, v[n-1].p);
			bool flag = true;
			int id = (i+1) * 2;

			REP(j, i+1, n-1) {
				if(s3.isIntersect(seg[j])) continue;
				flag = false;
			}

			if(flag) {
				double dist = seg[i].a.distance(v[n-1].p);
				G[n*2-1].push_back(edge(id-1, dist));
				G[id-1].push_back(edge(n*2-1, dist));
			}

			Seg s4(seg[i].b, v[n-1].p);
			flag = true;
			REP(j, i+1, n-1) {
				if(s4.isIntersect(seg[j])) continue;
				flag = false;
			}

			if(flag) {
				double dist = seg[i].b.distance(v[n-1].p);
				G[n*2-1].push_back(edge(id, dist));
				G[id].push_back(edge(n*2-1, dist));
			}
		}

		Seg s(v[0].p, v[n-1].p);
		bool flag = true;
		rep(i, n-1) {
			if(s.isIntersect(seg[i])) continue;
			flag = false;
		}

		if(flag) {
			double dist = v[0].p.distance(v[n-1].p);
			G[0].push_back(edge(n*2-1, dist));
			G[n*2-1].push_back(edge(0, dist));
		}

		dijkstra(0, n*2);

		cout << fixed;
		cout.precision(10);

		cout << d[n*2-1] << endl;
	}

	
	return 0;
}

Measured memory_bytes: 1732