Problem: There is a chain consisting of multiple circles on a plane. The first (last) circle of the chain only intersects with the next (previous) circle, and each intermediate circle intersects only with the two neighboring circles.

Your task is to find the shortest path that satisfies the following conditions.

* The path connects the centers of the first circle and the last circle.
* The path is confined in the chain, that is, all the points on the path are located within or on at least one of the circles.

Figure E-1 shows an example of such a chain and the corresponding shortest path.

<image>

Figure E-1: An example chain and the corresponding shortest path


Input

The input consists of multiple datasets. Each dataset represents the shape of a chain in the following format.

> n
>  x1 y1 r1
>  x2 y2 r2
>  ...
>  xn yn rn
>

The first line of a dataset contains an integer n (3 ≤ n ≤ 100) representing the number of the circles. Each of the following n lines contains three integers separated by a single space. (xi, yi) and ri represent the center position and the radius of the i-th circle Ci. You can assume that 0 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, and 1 ≤ ri ≤ 25.

You can assume that Ci and Ci+1 (1 ≤ i ≤ n−1) intersect at two separate points. When j ≥ i+2, Ci and Cj are apart and either of them does not contain the other. In addition, you can assume that any circle does not contain the center of any other circle.

The end of the input is indicated by a line containing a zero.

Figure E-1 corresponds to the first dataset of Sample Input below. Figure E-2 shows the shortest paths for the subsequent datasets of Sample Input.

<image>

Figure E-2: Example chains and the corresponding shortest paths


Output

For each dataset, output a single line containing the length of the shortest chain-confined path between the centers of the first circle and the last circle. The value should not have an error greater than 0.001. No extra characters should appear in the output.

Sample Input


10
802 0 10
814 0 4
820 1 4
826 1 4
832 3 5
838 5 5
845 7 3
849 10 3
853 14 4
857 18 3
3
0 0 5
8 0 5
8 8 5
3
0 0 5
7 3 6
16 0 5
9
0 3 5
8 0 8
19 2 8
23 14 6
23 21 6
23 28 6
19 40 8
8 42 8
0 39 5
11
0 0 5
8 0 5
18 8 10
8 16 5
0 16 5
0 24 5
3 32 5
10 32 5
17 28 8
27 25 3
30 18 5
0


Output for the Sample Input


58.953437
11.414214
16.0
61.874812
63.195179






Example

Input

10
802 0 10
814 0 4
820 1 4
826 1 4
832 3 5
838 5 5
845 7 3
849 10 3
853 14 4
857 18 3
3
0 0 5
8 0 5
8 8 5
3
0 0 5
7 3 6
16 0 5
9
0 3 5
8 0 8
19 2 8
23 14 6
23 21 6
23 28 6
19 40 8
8 42 8
0 39 5
11
0 0 5
8 0 5
18 8 10
8 16 5
0 16 5
0 24 5
3 32 5
10 32 5
17 28 8
27 25 3
30 18 5
0


Output

58.953437
11.414214
16.0
61.874812
63.195179

Solution (in CPP):

Solution:
#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);
	}
}