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 <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define lengthof(array) (sizeof(array) / sizeof(*array))
#define dump(a) (cerr << (#a) << " = " << (a) << endl)
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin(); it!=(c).end();++it)
#define RFOR(it,c) for(__typeof((c).rbegin())it=(c).rbegin(); it!=(c).rend();++it)

template<class T> inline void chmax(T& a, T b) { if(b > a) a = b; }
template<class T> inline void chmin(T& a, T b) { if(b < a) a = b; }

template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << '(' << p.first << ", " << p.second << ')';
	return os;
}

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	copy(v.begin(), v.end(), ostream_iterator<T>(os, " "));
	return os;
}

const double EPS = 1e-9;
struct point {
	double x, y;
	point():x(0), y(0) {}
	point(double x, double y):x(x), y(y) {}
	point(const point& p):x(p.x), y(p.y) {}

	point operator+ (const point& p) const {
		return point(x + p.x, y + p.y);
	}

	point operator- (const point& p) const {
		return point(x - p.x, y - p.y);
	}

	point operator* (const double s) const {
		return point(x * s, y * s);
	}

	point operator* (const point& p) const {
		return point(x * p.x - y * p.y, x * p.y + y * p.x);
	}

	point operator/ (const double s) const {
		return point(x / s, y / s);
	}

	bool operator< (const point& p) const {
		return x + EPS < p.x || abs(x - p.x) < EPS && y + EPS < p.y;
	}

	bool operator== (const point& p) const {
		return abs(x - p.x) < EPS && abs(y - p.y) < EPS;
	}
};

point rotate90(const point& p) {
	return point(-p.y, p.x);
}

point rotate(const point& p, const double theta) {
	const double s = sin(theta), c = cos(theta);
	return point(c * p.x - s * p.y, s * p.x + c * p.y);
}

double angle(const point& p) {
	return atan2(p.y, p.x);
}

double abs(const point& p) {
	return sqrt(p.x * p.x + p.y * p.y);
}

double norm(const point& p) {
	return p.x * p.x + p.y * p.y;
}

double dot(const point& l, const point& r) {
	return l.x * r.x + l.y * r.y;
}

double cross(const point& l, const point& r) {
	return l.x * r.y - l.y * r.x;
}

struct line {
	point a, b;
	line(point a, point b):a(a), b(b){}
};

struct segment {
	point a, b;
	segment(point a, point b):a(a), b(b){}
};

struct circle {
	point c;
	double r;
	circle():c(point(0, 0)), r(0.0){}
	circle(point c, double r):c(c), r(r){}
};

typedef vector<point> polygon;

int ccw(const point& a, point b, point c) {
	b = b - a;
	c = c - a;
	if(cross(b, c) > EPS) return 1; // ccw
	if(cross(b, c) < -EPS) return -1; // cw
	if(dot(b, c) < 0) return 2; // c, a, b 順に一直線上
	if(norm(b) < norm(c)) return -2; // a, b, c 順に一直線上
	return 0; //a, c, b 順で一直線上
}

point projection(const line& l, const point& p) {
	const point dif = l.b - l.a;
	const double tmp = dot(p - l.a, dif) / norm(dif);
	return l.a + dif * tmp;
}

bool intersect(const line& l, const line& m) {
	return abs(cross(l.b - l.a, m.b - m.a)) > EPS || abs(cross(l.b - l.a, m.b - l.a)) < EPS;
}

bool intersect(const line& l, const segment& s) {
	return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS;
}

bool intersect(const line& l, const point& p) {
	return abs(ccw(l.a, l.b, p)) != -1;
}

bool intersect(const segment& s, const segment& t) {
	return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
		ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

bool intersect(const segment& s, const point& p) {
	return ccw(s.a, s.b, p) == 0;
}

bool intersect(const circle& c, const point& p) {
	return abs(c.c - p) <= c.r + EPS;
}

bool intersect(const circle& c, const circle& d) {
	return abs(c.c - d.c) <= c.r + d.r && abs(c.c - d.c) >= abs(c.r - d.r);
}

double dist(const point& a, const point& b) {
	return abs(a - b);
}

double dist(const line& l, const point& p) {
	return abs(p - projection(l, p));
}

double dist(const line& l, const line& m) {
	return intersect(l, m) ? 0 : dist(l, m.a);
}

double dist(const line& l, const segment& s) {
	return intersect(l, s) ? 0 : min(dist(l, s.a), dist(l, s.b));
}

double dist(const segment& s, const point& p) {
	const point tmp = projection(line(s.a, s.b), p);
	return intersect(s, tmp) ? abs(tmp - p) : min(abs(s.a - p), abs(s.b - p));
}

double dist(const segment& s, const segment& t) {
	if(intersect(s, t))
		return 0;
	return min(min(dist(s, t.a), dist(s, t.b)), min(dist(t, s.a), dist(t, s.b)));
}

point crosspoint(const line& l, const line& m) {
	const double tmp = cross(l.b - l.a, m.b - m.a);
	if(abs(tmp) < EPS) // 平行
		return l.a;
	return l.a + (l.b - l.a) * cross(m.b - m.a, m.b - l.a) * (1.0 / tmp);
}

point crosspoint(const segment& s, const segment& t) {
	if(!intersect(s, t)) // 交点を持たない
		return s.a; // 用改善

	const double tmp = cross(s.b - s.a, t.b - t.a);
	if(abs(tmp) < EPS) { // 一直線上
		if(intersect(s, t.a)) return t.a;
		if(intersect(s, t.b)) return t.b;
		if(intersect(t, s.a)) return s.a;
		return s.b;
	}

	return s.a + (s.b - s.a) * cross(s.b - s.a, s.b - t.a) * (1.0 / tmp);
}

vector<point> crosspoint(const circle &c, const circle& d) {
	vector<point> res;
	if(abs(c.c - d.c) < EPS) // 中心の座標が同じ
		return res;

	const double tmp = abs(c.c - d.c);
	const double rc = (tmp * tmp + c.r * c.r - d.r * d.r) / (tmp + tmp);
	const double rs = sqrt(c.r * c.r - rc * rc);
	const point diff = (d.c - c.c) / tmp;
	res.push_back(point(c.c + diff * point(rc, rs)));
	res.push_back(point(c.c + diff * point(rc, -rs)));
	return res;
}

vector<point> crosspoint(const circle& c, const line& l) {
	vector<point> res;
	const point h = projection(l, c.c);
	const double d = abs(h - c.c);
	if(d > c.r - EPS) {
		res.push_back(h);
	}
	else if(d <= c.r - EPS) {
		point v = l.b - l.a;
		v = v * sqrt(c.r * c.r - d * d) / abs(v);
		res.push_back(h + v);
		res.push_back(h - v);
	}

	return res;
}

vector<point> crosspoint(const circle& c, const segment& s) {
	vector<point> res;
	vector<point> tmp = crosspoint(c, line(s.a, s.b));
	for(int i = 0; i < tmp.size(); ++i)
		if(intersect(s, tmp[i]))
			res.push_back(tmp[i]);

	return res;
}

double area(const polygon& p) {
	double res = 0.0;
	const int num = p.size();
	for(int i = 0; i < num; ++i) {
		res += cross(p[i], p[(i + 1) % num]);
	}

	return res * 0.5;
}

vector<circle> circles;
vector<vector<point> > c_p;

struct edge {
	int to;
	double cost;
	edge(int t, double c):to(t), cost(c){}
};
typedef pair<int, int> P;

vector<vector<edge> > es;

double dijkstra(int s, int t) {
	priority_queue<P, vector<P>, greater<P> > que;
	vector<double> d(es.size(), INT_MAX);
	que.push(P(0, s));
	d[s] = 0;
	
	while(!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if(d[v] < p.first)
			continue;

		if(v == t)
			return d[t];

		for(int i = 0; i < es[v].size(); ++i) {
			edge& e = es[v][i];
			if(d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}

	return -1;
}

inline bool in_range(const segment& s, const point& p, const point& q) {
	int tmp = ccw(s.a, s.b, p) * ccw(s.a, s.b, q);
	return tmp == -1 || tmp == 0;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	for(int n; scanf("%d", &n), n;) {
		circles.clear();
		circles.resize(n);
		for(int i = 0; i < n; ++i) {
			int x, y, r;
			scanf("%d %d %d", &x, &y, &r);
			circles[i] = circle(point(x, y), r);
		}

		c_p.clear();
		c_p.resize(n - 1, vector<point>(2));
		for(int i = 0; i < n - 1; ++i) {
			vector<point> tmp = crosspoint(circles[i], circles[i + 1]);
			c_p[i][0] = tmp[0];
			c_p[i][1] = tmp[1];
		}

		es.clear();
		es.resize(2 * n + 2);

		for(int i = 0; i < n - 1; ++i)
			for(int j = 0; j <= 1; ++j)
				for(int k = i + 1; k < n - 1; ++k)
					for(int l = 0; l <= 1; ++l) {
						const segment s(c_p[i][j], c_p[k][l]);
						for(int m = i + 1; m < k; ++m)
							if(!in_range(s, c_p[m][0], c_p[m][1]))
								goto ng;

						es[i + j * n].push_back(edge(k + l * n, dist(s.a, s.b)));
					ng:;
					}


		for(int i = 0; i < n - 1; ++i)
			for(int j = 0; j <= 1; ++j) {
				const segment s(circles[0].c, c_p[i][j]);
				for(int m = 0; m < i; ++m)
					if(!in_range(s, c_p[m][0], c_p[m][1]))
						goto ng2;

				es[2 * n].push_back(edge(i + j * n, dist(s.a, s.b)));
			ng2:;
			}


		for(int i = 0; i < n - 1; ++i)
			for(int j = 0; j <= 1; ++j) {
				const segment s(c_p[i][j], circles[n - 1].c);
				for(int m = i + 1; m < n - 1; ++m) {
					if(!in_range(s, c_p[m][0], c_p[m][1]))
						goto ng3;
				}
				es[i + j * n].push_back(edge(2 * n + 1, dist(s.a, s.b)));
			ng3:;
			}

		{
			const segment s(circles[0].c, circles[n - 1].c);
			for(int i = 0; i < n - 1; ++i) {
				if(!in_range(s, c_p[i][0], c_p[i][1]))
					goto ng4;
			}
			es[2 * n].push_back(edge(2 * n + 1, dist(s.a, s.b)));
		ng4:;
		}

		printf("%.10lf\n", dijkstra(2 * n, 2 * n + 1));
	}

	return EXIT_SUCCESS;
}