#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <complex>
#include <cmath>
#include <algorithm>
using namespace std;

// * XY座標
#define X real()
#define Y imag()

// * 点の表現
typedef complex<double> P;

// * 許容する誤差ε
const double EPS = 1e-10;
// * Infinity
const double INF = 1e12;
// * 円周率
const double PI = acos(-1.0);
// * Infinity 2
const P INF_P(INF,INF);

// * complex<double> の順序を定義する
namespace std {
	bool operator < (const P& a, const P& b) {
		return (real(a) != real(b))? real(a) < real(b) : imag(a) < imag(b);
	}
}

// * 2点間の距離
double dist(P p1, P p2) {
	return abs(p1 - p2);
}

// * 2つのスカラーが等しいかどうか
bool equal(double a, double b) {
	return ( fabs( a - b ) < EPS );
}
// * 内積 (dot product) : a・b = |a||b|cosΘ
double dot(P a, P b) {
	return real( conj(a) * b );
}
// * 外積 (cross product) : a×b = |a||b|sinΘ
double cross(P a, P b) {
	return imag( conj(a) * b ) ;
}

// CCW : 反時計回り (Counter Clock Wise)
// CW : 時計回り (Clock Wise)
enum {CCW=1, CW=-1, ON=0};
// * 3点がどちら回りであるか返す, 3点が1直線に乗っているときは ON を返す
int ccw(const P &a, P b, P c) {
    b-=a, c-=a;
    if( cross(b,c) >  EPS ) return CCW; // CCW : 反時計回り
    if( cross(b,c) < -EPS ) return CW;  // CW : 時計回り
    if(dot(b, c) < -EPS )   return +2;  // c--a--b on line
    if(dot(b, b) + EPS < dot(c, c) ) return -2; // a--b--c on line 
    return ON;
}
// 線分の表現
struct Segment{
	// 点 a, b を端点とする線分
	P a, b;
	// コンストラクタで初期化
	Segment(P a_, P b_) { a = a_; b = b_; }
	// 点 p が線分上にあるかどうか
	bool contain(P p) { return (abs(a-p) + abs(p-b) < abs(a-b) + EPS); }
	// 線分と点 p の距離
	double distance(P p) {
		if( dot(b-a, p-a) < EPS ) return abs(p-a);
		if( dot(a-b, p-b) < EPS ) return abs(p-b);
		return abs(cross(b-a, p-a)) / abs(b-a);
	}
	// 線分 s と交差しているかどうかを返す.
    bool is_intersection(const Segment& s){
        return ( ccw(a, b, s.a)   * ccw(a, b, s.b) <= 0 && 
                 ccw(s.a, s.b, a) * ccw(s.a, s.b, b) <= 0 );
    }
};
// 円の表現
struct Circle{
	// 円の中心
	P p;
	// 円の半径
	double r;
	// コンストラクタで初期化
	Circle(P p_, double r_) { p = p_; r = r_; }
	Circle(){}
	// 円の面積
	double get_area() { return r * r * PI; }
	// 円周
	double circumference() { return 2.0 * r * PI; }
	// 点 a が円の内部にあるかどうか
	bool is_inside(P a) { return ( dist(a,p) <= r ); }
	// 点 a が円周上にあるかどうか
	bool on_boundary(P a) { return equal( dist(a,p) , r ); }
	// 2つの円の位置関係
	// 2 つの円が離れている => 0
	// 2 つの円が外接する   => 1
	// 2 つの円が交わる     => 2
	// 2 つの円が内接する    => 3 (2つの円が等しいときは内接)
	// 円が含まれている       => 4
	int is_pos(const Circle& c) {
		double d = abs(p - c.p);
		if( r + c.r + EPS < d ) { // 離れている
			return 0;
		}else if( equal( r + c.r , d ) ) { // 外接する
			return 1;
		}else if( equal( fabs(r-c.r) , d ) ) { // 内接する
			return 3;
		}else if( d < fabs(r-c.r) ) { // 含まれる
			return 4;
		}else { // 交わる	
			return 2;
		}
	}
	// 2 つの円の交わる点を返す
	// 2 つの円が離れている・内包する => 交点は 0 個, (INF_P,INF_P) を返す.
	// 2 つの円が外接 or 内接する   => 交点は 1 個, (firstとsecondに同じ値が入る)
	// 2 つの円が交わる            => 交点は 2 個.
	// 2 つの円は等しい            => 交点は 無限 個, (INF_P,INF_P) を返す.
	pair<P,P> intersection(const Circle& c) {
		double d = abs( p - c.p );
		double rc = ( d*d + r*r - c.r*c.r ) / (2.0*d);
		double rs = sqrt( r*r - rc*rc );
		P diff = (c.p - p) / d;
		return pair<P,P> ( p + diff * P(rc, rs) , p + diff * P(rc, -rs) );
	}
};

// 円 i の 交点 p1 から 円 j の交点 p2 まで直線で移動できるかどうかを返す.
bool is_move(vector<Segment>& vs, int i, int j, P p1, P p2){
	Segment s(p1,p2);
	for(int k=i+1 ; k < j ; k++ ){
		if( !vs[k].is_intersection(s) ){
			return false;
		}
	}
	return true;
}

// スタート sp から 円 i の交点 p1 まで直線で移動できるかどうか
bool is_start_to_p(vector<Segment>& vs, P sp, int i, P p1){
	Segment s(sp,p1);
	for(int k=0 ; k < i ; k++ ){
		if( !vs[k].is_intersection(s) ){
			return false;
		}
	}
	return true;
}

// ゴール gp から 円 i の交点 p1 まで直線で移動できるかどうか
bool is_goal_to_p(vector<Segment>& vs, P gp, int i, P p1){
	Segment s(gp,p1);
	for(int k=vs.size()-1 ; i < k ; k-- ){
		if( !vs[k].is_intersection(s) ){
			return false;
		}
	}
	return true;
}

// スタート sp から ゴール gp まで直線で移動できるかどうか
bool is_start_to_goal(vector<Segment>& vs, P sp, P gp){
	Segment s(sp,gp);
	for(int k=0 ; k < vs.size() ; k++ ){
		if( !vs[k].is_intersection(s) ){
			return false;
		}
	}
	return true;
}

// グラフの最大の頂点数
const int MAX_V = 210;
// グラフ
double G[MAX_V][MAX_V];

// 初期化
void ini(){
	for(int i=0 ; i < MAX_V ; i++ ){
		for(int j=0 ; j < MAX_V ; j++ ){
			G[i][j] = (i == j)? 0 : INF;
		}
	}
}

// 辺の追加
void add_edge(int u, int v, double cost){
	G[u][v] = G[v][u] = cost;
}

// ワーシャルフロイド法
double warshall_floyd(int V, int s, int g){
	for(int k=0 ; k < V ; k++ ){
		for(int i=0 ; i < V ; i++ ){
			for(int j=0 ; j < V ; j++ ){
				G[i][j] = min( G[i][j] , G[i][k] + G[k][j] );
			}
		}
	}
	return G[s][g];
}

int main(){
	int n;
	while( scanf("%d", &n) , n ){
		ini();
		P sp, gp;
		vector<Circle> v(n);
		vector<Segment> vs;
		
		for(int i=0 ; i < n ; i++ ){
			int x, y, r;
			scanf("%d %d %d", &x, &y, &r );
			v[i] = Circle( P(x,y) , r );
			if( i == 0 ) sp = P(x,y);
			if( i == n-1 ) gp = P(x,y);
		}
		for(int i=1 ; i < n ; i++ ){
			pair<P,P> pp = v[i-1].intersection( v[i] );
			vs.push_back( Segment( pp.first , pp.second ) );
		}
		
		// 直線でスタートからゴールに行ける時
		if( is_start_to_goal(vs, sp, gp) ){
			double ans = dist(sp,gp);
			printf("%.6f\n", ans);
			continue;
		}
		
		int g = 2 * vs.size() + 1;
		// 直線で移動できる2点をエッジとしたグラフをつくる
		for(int i=0 ; i < vs.size() ; i++ ){
			P p1 = vs[i].a;
			P p2 = vs[i].b;
			int u = 2*i + 1;
			int v = 2*i + 2;
			if( is_start_to_p(vs, sp, i, p1) ){
				add_edge( 0 , u , dist(sp,p1) );
			}
			if( is_start_to_p(vs, sp, i, p2) ){
				add_edge( 0 , v , dist(sp,p2) );
			}
			if( is_goal_to_p(vs, gp, i, p1) ){
				add_edge( g , u , dist(gp,p1) );
			}
			if( is_goal_to_p(vs, gp, i, p2) ){
				add_edge( g , v , dist(gp,p2) );
			}
			for(int j=i+1 ; j < vs.size() ; j++ ){
				P p3 = vs[j].a;
				P p4 = vs[j].b;
				int u2 = 2*j + 1;
				int v2 = 2*j + 2;
				if( is_move(vs, i, j, p1, p3) ){
					add_edge( u , u2 , dist(p1,p3) );
				}
				if( is_move(vs, i, j, p1, p4) ){
					add_edge( u , v2 , dist(p1,p4) );
				}
				if( is_move(vs, i, j, p2, p3) ){
					add_edge( v , u2 , dist(p2,p3) );
				}
				if( is_move(vs, i, j, p2, p4) ){
					add_edge( v , v2 , dist(p2,p4) );
				}
			}
		}
		double ans = warshall_floyd( g+1 , 0 , g );
		printf("%.6f\n", ans);
	}
}

Measured memory_bytes: 1604