#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <stdio.h>
#define inf 1e9
#define eps 1e-9

using namespace std;
typedef pair<double, int> P;

struct vec2d{
	double x, y;
	vec2d(){}
	vec2d(double x, double y){
		this->x = x, this->y = y;
	}
	double add(double a, double b){
		if(fabs(a+b) < eps * (fabs(a) + fabs(b))) return 0.0;
		return a+b;
	}
	vec2d operator+(vec2d ope){
		return vec2d(add(x, ope.x), add(y, ope.y));
	}
	vec2d operator-(vec2d ope){
		return vec2d(add(x, -ope.x), add(y, -ope.y));
	}
	vec2d operator*(double t){
		return vec2d(x*t, y*t);
	}
	vec2d operator/(double t){
		return vec2d(x/t, y/t);
	}
	double dot(vec2d ope){
		return add(x*ope.x, y*ope.y);
	}
	double cross(vec2d ope){
		return add(x*ope.y, -y*ope.x);
	}
	double norm(){
		double d2 = dot(*this);
		if(d2 > 0) return sqrt(d2);
		return 0.0;
	}
};

double distPP(vec2d p, vec2d q){
	return (p-q).norm();
}

double distSP(vec2d p, vec2d q, vec2d x)
{
	if((x-p).dot(q-p) <= 0) return distPP(p, x);
	if((x-q).dot(p-q) <= 0) return distPP(q, x);
	return fabs( (x-p).cross(q-p) / distPP(p, q) );
}

bool isOnS(vec2d p, vec2d q, vec2d x)
{
	return (p-x).cross(q-x) == 0 && (p-x).dot(q-x) <= 0;
}

bool isCross(vec2d p, vec2d q, vec2d r, vec2d s)
{
	if((q-p).cross(s-r) == 0){
		return isOnS(p, q, r) || isOnS(p, q, s) || isOnS(r, s, p) || isOnS(r, s, q);	
	}
	double t = (r-p).cross(s-r) / (q-p).cross(s-r);
	vec2d x = p + (q-p)*t;
	return isOnS(p, q, x) && isOnS(r, s, x);
}

struct edge{
	int to;
	double cost;
	edge(){}
	edge(int a, double b){
		to = a, cost = b;
	}
};

int n;
vec2d p[105];
double r[105];

int V;
vector< pair<vec2d, int> > cp;
vector<edge> G[205];
double dist[205];

void dijkstra()
{
	for(int i = 0; i < cp.size(); i++) dist[i] = inf;
	dist[0] = 0;
	priority_queue< P, vector<P>, greater<P> > Q;
	Q.push( make_pair(0, 0) );
	
	int v; double d;
	while(Q.size()){
		v = Q.top().second;
		d = Q.top().first;
		Q.pop();
		if(dist[v] < d) continue;
		for(int i = 0; i < G[v].size(); i++){
			if(dist[G[v][i].to] > d + G[v][i].cost){
				dist[G[v][i].to] = d + G[v][i].cost;
				Q.push( make_pair(dist[G[v][i].to], G[v][i].to) );
			}
		}
	}
}

int main(void)
{
	while(1){
		cin >> n;
		if(n == 0) break;
		
		for(int i = 0; i < n; i++){
			cin >> p[i].x >> p[i].y >> r[i];
		}
		
		cp.clear();
		cp.push_back( make_pair(p[0], -1) );
		cp.push_back( make_pair(p[n-1], n) );
		
		vec2d l, nl, c1, c2;
		double x, L, h;
		for(int i = 0; i < n-1; i++){
			L = distPP(p[i], p[i+1]);
			x = (L*L + r[i+1]*r[i+1] - r[i]*r[i]) / (2*L);
			h = sqrt(r[i+1]*r[i+1] - x*x);
			
			l = p[i+1] - p[i];
			l = l / l.norm();
			nl.x = l.y, nl.y = -l.x;
			
			c1 = p[i] + l*(L-x) + nl*h;
			c2 = p[i] + l*(L-x) - nl*h;
			cp.push_back( make_pair(c1, i) );
			cp.push_back( make_pair(c2, i) );
		}
		
		double d;
		for(int i = 0; i < cp.size(); i++) G[i].clear();
		for(int i = 0; i < cp.size(); i++){
			for(int j = 0; j < cp.size(); j++){
				if(i >= j) continue;
				bool flag = true;
				int s = min(cp[i].second, cp[j].second);
				int t = max(cp[i].second, cp[j].second);
				for(int k = s+1; k <= t-1; k++){
					if(k < 0 || k >= n-1) continue;
					if(!isCross(cp[i].first, cp[j].first, cp[2*(k+1)].first, cp[2*(k+1)+1].first)){
						flag = false;
						break;
					}
				}
				if(!flag) continue;
				d = distPP(cp[i].first, cp[j].first);
				G[i].push_back( edge(j, d) );
				G[j].push_back( edge(i, d) );
			}
		}
		dijkstra();
		
		printf("%.8f\n", dist[1]);
	}
	
	return 0;
}

Measured memory_bytes: 3436