#include <iostream>
#include <vector>
#include <array>
#include <complex>
#include <cmath>
#include <iomanip>

using Comp = std::complex<double>;

constexpr double Eps = 0.00000001;
constexpr double Inf = 1000000000;

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

bool intersects(const Comp& s1, const Comp& l1, const Comp& s2, const Comp& l2) {
	double c12 = cross(l1, l2);
	if (std::abs(c12) <= Eps)
		return false;

	const Comp l = s2 - s1;
	double t1 = cross(l, l1) / c12;
	double t2 = cross(l, l2) / c12;
	return 0 <= t1 && t1 <= 1 && 0 <= t2 && t2 <= 1;
}

struct Circle {
	Comp center;
	double r;

	std::array<Comp, 2> intersections(const Circle& c) const {
		double l = std::abs(c.center - center);
		Comp n_l = (c.center - center) / l;

		double theta = std::acos((r*r + l * l - c.r * c.r)/(2*r*l));

		return {
			center + std::polar(r, theta) * n_l,
			center + std::polar(r, -theta)* n_l
		};
	}
};

int main() {
	int n;
	while (std::cin >> n, n != 0) {
		std::vector<Circle> circles(n);
		for (auto&& c : circles) {
			int x, y;
			std::cin >> x >> y >> c.r;
			c.center = Comp(x, y);
		}

		std::vector<std::array<Comp, 2>> iss(n - 1);
		for (int i = 0; i < n - 1; ++i)
			iss[i] = circles[i].intersections(circles[i + 1]);

		auto isValid = [&](const Comp& a, const Comp b, int s, int t) {
			for (int i = s; i < t; ++i)
				if (!intersects(a, b - a, iss[i][0], iss[i][1] - iss[i][0]))
					return false;

			return true;
		};

		std::vector<std::array<double, 2>> dp(n - 1, {Inf, Inf});

		dp[0][0] = std::abs(iss[0][0] - circles[0].center);
		dp[0][1] = std::abs(iss[0][1] - circles[0].center);
		for (int i = 2; i / 2 < n - 1; ++i) {
			if (isValid(circles[0].center, iss[i / 2][i % 2], 0, i / 2))
				dp[i / 2][i % 2] = std::abs(iss[i / 2][i % 2] - circles[0].center);

			for (int j = 0; j / 2 < i / 2; ++j) {
				if (isValid(iss[j / 2][j % 2], iss[i / 2][i % 2], j / 2 + 1, i / 2)) {
					dp[i / 2][i % 2] = std::min(
						dp[i / 2][i % 2],
						dp[j / 2][j % 2] + std::abs(iss[i / 2][i % 2] - iss[j / 2][j % 2])
					);
				}
			}
		}

		double ans = Inf;
		if (isValid(circles[0].center, circles[n - 1].center, 0, n - 1))
			ans = std::abs(circles[n - 1].center - circles[0].center);

		for (int i = 0; i / 2 < n - 1; ++i) {
			if (isValid(iss[i / 2][i % 2], circles[n - 1].center, i / 2 + 1, n - 1)) {
				ans = std::min(
					ans,
					dp[i / 2][i % 2] + std::abs(circles[n - 1].center - iss[i / 2][i % 2])
				);
			}
		}

		std::cout << std::fixed << std::setprecision(6) << ans << std::endl;
	}
}
