#include <iostream>
#include <cstdio>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define double long double
using namespace std;
typedef complex<double> Point;
typedef vector<Point> Points;

int n;
Point c[100]; double r[100];

double dot(Point a, Point b) {
	return a.real() * b.real() + a.imag() * b.imag();
}

double cross(Point a, Point b) {
	return a.real() * b.imag() - a.imag() * b.real();
}

//a->b->cの曲がる方向。反時計回り, 180°折り返しは正.
const double EPS = 1e-10;		//大体, 座標範囲^2 / 10^(-16)くらいにしておくと無難？
//それぞれの条件を厳しめにしておくと, 線分交差判定はちょっと緩めにYesを返すようになったりして吉.
int ccw(Point a, Point b, Point c) {
	b -= a;
	c -= a;
	
	if (cross(b, c) > EPS) return +1;
	if (cross(b, c) < -EPS) return -1;
	if (dot(b, c) < -EPS) return +2;		//c--b--a
	if (norm(b) < norm(c) - EPS) return -2;	//a--b--c
	return 0;
}

//線分の交差判定. ギリギリ重ならない場合も重なると判定しておく.
bool intersect_SS(Point a, Point b, Point c, Point d) {
	return ccw(a, b, c) * ccw(a, b, d) <= 0 && ccw(c, d, a) * ccw(c, d, b) <= 0;
}

//円と直線の交点. 相異なる2点が交点になると仮定.
vector<Point> kouten_CL(Point c, double r, Point s, Point e) {
	s -= c;
	e -= c;
	
	double dt = dot(s, e - s);
	double nm = norm(e - s);
	double D = sqrt(dt * dt - nm * (norm(s) - r * r));
	double alpha1 = (-dt - D) / nm;
	double alpha2 = (-dt + D) / nm;
	
	Point res1 = s + alpha1 * (e - s);
	Point res2 = s + alpha2 * (e - s);
	vector<Point> ret;
	ret.push_back(res1 + c);
	ret.push_back(res2 + c);
	return ret;
}

//円と円の交点. 相異なる2点が交点になると仮定.
vector<Point> kouten_CC(Point c1, double r1, Point c2, double r2) {
	Point r = c2 - c1;
	double theta = acos((norm(r) + r1 * r1 - r2 * r2) / (2 * r1 * abs(r)));
	Point R = (r1 / abs(r)) * r;
	Point res1 = R * exp(Point(0, 1) * theta);
	Point res2 = R * exp(Point(0, 1) * (-theta));
	vector<Point> ret;
	ret.push_back(res1 + c1);
	ret.push_back(res2 + c1);
	return ret;
}

int toId(int i) {	//点solve.ps[i]が何番(>=0)の円に乗ってるか
	if (i == 0) return 0;
	if (i == 2 * n - 1) return n - 1;
	return (i - 1) / 2 + 1;
}

bool can_connect(int i, int j, Point s, Point e) {
	i = toId(i);
	j = toId(j);
	
	vector<Point> ps;
	for (int k = i; k <= j; k++) {
		double crs = cross(e - s, c[k] - s);
		if (crs * crs > r[k] * r[k] * norm(e - s)) return false;
		if (crs * crs == r[k] * r[k] * norm(e - s)) {
			if (k == j) return true;
			return false;
		}
		vector<Point> p = kouten_CL(c[k], r[k], s, e);
		ps.push_back(p[0]);
		ps.push_back(p[1]);
	}
	
	for (int k = 0; k + 3 < ps.size(); k += 2) {
		//誤差がなければ…、ギリギリ重なる場合はあって、ギリギリ重ならない場合はたぶん無い
		//ギリギリ重なる場合、誤差があるとギリギリ重ならないケースになるので、緩めにYes判定する.
		if (intersect_SS(ps[k], ps[k + 1], ps[k + 2], ps[k + 3]) == false) {
			return false;
		}
	}
	return true;
}

double solve() {
	int i, j;
	vector<Point> ps;
	vector<int> et[200];
	vector<double> ec[200];

	ps.push_back(c[0]);
	rep(i, n - 1) {
		Points p = kouten_CC(c[i], r[i], c[i + 1], r[i + 1]);
		ps.push_back(p[0]);
		ps.push_back(p[1]);
	}
	ps.push_back(c[n - 1]);
	
	/*rep(i, 2 * n) {
		cout << "ps[" << i << "] = (" << ps[i].real() << ", " << ps[i].imag() << ")" << endl;
	}*/
	
	rep(i, 2 * n) {
		for (j = i + 1; j < 2 * n; j++) {
			if (can_connect(i, j, ps[i], ps[j])) {
				double dist = abs(ps[j] - ps[i]);
				et[i].push_back(j);
				ec[i].push_back(dist);
				//cout << i << "->" << j << endl;
			}
		}
	}
	
	//DAGなので、ダイクストラは不要
	double dp[200];
	double INF = 1145141919;
	rep(i, 2 * n) dp[i] = INF;
	dp[0] = 0;
	rep(i, 2 * n) {
		rep(j, et[i].size()) {
			int nxt = et[i][j];
			dp[nxt] = min(dp[nxt], dp[i] + ec[i][j]);
		}
	}
	return dp[2 * n - 1];
}

signed main() {
	while (cin >> n) {
		if (!n) break;
		
		int i;
		rep(i, n) {
			double x, y;
			cin >> x >> y >> r[i];
			c[i] = Point(x, y);
		}
		double res = solve();
		printf("%.14Lf\n", res);
	}
	return 0;
}


Measured memory_bytes: 3648