#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

struct Angle {
	long double sin, cos;
	Angle operator+(const Angle& that) const { return Angle{ sin * that.cos + cos * that.sin, cos * that.cos - sin * that.sin }; }
	Angle operator-(const Angle& that) const { return Angle{ sin * that.cos - cos * that.sin, cos * that.cos + sin * that.sin }; }
	static Angle from_sin(const long double sin);
};
Angle Angle::from_sin(const long double sin) {
	return Angle{ sin, std::sqrt(1 - sin * sin) };
}
struct Vector {
	long double x, y;
	long double cross(const Vector& that) const { return x * that.y - y * that.x; }
	long double dot(const Vector& that) const { return x * that.x + y * that.y; }
	long double length() const { return std::sqrt(x * x + y * y); }
	Angle angle() const { return Angle{ y / length(), x / length() }; }
};
struct Coordinate {
	long double x, y;
	Vector operator-(const Coordinate& that) const { return Vector{ x - that.x, y - that.y }; }
	Coordinate operator+(const Coordinate& that) const { return Coordinate{ x + that.x, y + that.y }; }
	long double distance(const Coordinate& that) const { return (*this - that).length(); }
};
long double inner_area(const long double a, const long double b, const long double c) {
	auto s = (a + b + c) / 2;
	return std::sqrt(s * (s - a) * (s - b) * (s - c));
}
int sign(const long double val) { return (val == 0) ? 0 : (std::signbit(val)) ? -1 : 1; }
struct Edge {
	Coordinate from, to;
	bool is_cross(const Edge& that) const {
		constexpr long double eps = 0.0000000001;
		return sign((to - from).cross(that.to - from)) * sign((to - from).cross(that.from - from)) <= 0 && sign((that.to - that.from).cross(to - that.from)) * sign((that.to - that.from).cross(from - that.from)) <= 0;
	}
	long double length() const {
		return (from - to).length();
	}
	Coordinate operator[](const int index) const {
		return (index == 0) ? from : to;
	}
};
struct Circle {
	Coordinate center;
	long double radius;
	Edge cut(const Circle& that) const {
		auto mid = that.center - center;
		auto catheti = inner_area(radius, that.radius, mid.length()) * 2 / mid.length();
		auto diff_angle = Angle::from_sin(catheti / radius);
		auto mid_angle = mid.angle();
		auto a = mid_angle + diff_angle;
		auto b = mid_angle - diff_angle;
		return Edge{ Coordinate{a.cos * radius, a.sin * radius} + center, Coordinate{b.cos * radius, b.sin * radius} + center };
	}
};
long double min_length(const std::vector<Edge>& edges, const std::pair<int, int> &start, const Coordinate& goal, std::vector<std::vector<long double>>& memo) {
	if (memo[start.first][start.second] >= 0) return memo[start.first][start.second];
	else {
		memo[start.first][start.second] = LDBL_MAX;
		auto current = edges[start.first][start.second];
		auto to_goal = Edge{ current, goal };
		auto is_cross = true;
		for (auto i = start.first + 1; i < edges.size() && is_cross; ++i) {
			if (!edges[i].is_cross(to_goal)) {
				is_cross = false;
			}
		}
		if (is_cross) return memo[start.first][start.second] = to_goal.length();
		for (auto next = start.first + 1; next < edges.size(); ++next) {
			for (auto i = 0; i < 2; ++i) {
				auto to_next = Edge{ current, edges[next][i] };
				is_cross = true;
				for (auto mid = start.first + 1; mid < next; ++mid) {
					if (!edges[mid].is_cross(to_next)) {
						is_cross = false;
					}
				}
				if (is_cross) {
					memo[start.first][start.second] = std::min(memo[start.first][start.second], min_length(edges, std::make_pair(next, i), goal, memo) + to_next.length());
				}
			}
		}
		return memo[start.first][start.second];
	}
}
int main() {
	while (true) {
		int n; std::cin >> n; if (n == 0) return 0;
		std::vector<Circle> circles(n); for (auto& c : circles) std::cin >> c.center.x >> c.center.y >> c.radius;
		std::vector<Edge> edges; edges.push_back(Edge{ circles.front().center, circles.front().center });
		for (auto i = 1; i < n; ++i) {
			edges.push_back(circles[i].cut(circles[i - 1]));
		}
		std::vector<std::vector<long double>> memo(n, std::vector<long double>(2, -1));
		std::cout << std::setprecision(16) << std::fixed << min_length(edges, std::make_pair(0, 0), circles.back().center, memo) << std::endl;
	}
}


Measured memory_bytes: 3344