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 <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
#include <cassert>
#include <complex>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

#define X real()
#define Y imag()

typedef complex<double> point;
const double EPS = 1e-9;

namespace std {
	bool operator==(const point &p, const point &q) {
		return abs(p.X - q.X) < EPS && abs(p.Y - q.Y) < EPS;
	}

	bool operator!=(const point &p, const point &q) {
		return !(p == q);
	}

	bool operator<(const point &p, const point &q) {
		return p.X + EPS < q.X || abs(p.X - q.X) < EPS && p.Y + EPS < q.Y;
	}

	bool operator>(const point &p, const point &q) {
		return q < p;
	}
}

double dot(const point &l, const point &r) {
	return real(conj(l)*r);
}

double cross(const point &l, const point &r) {
	return imag(conj(l)*r);
}

point rotate90(const point &p)
{
	return point(-p.Y, p.X);
}

point rotate(const point &p, const double theta)
{
	return polar(abs(p), arg(p)+theta);
}

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

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

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

typedef vector<point> polygon;

inline int ccw(const point& a, point b, point c) {
	b = b - a;
	c = c - a;
	const double tmp = cross(b, c);
	if(tmp > EPS) return 1; // ccw
	if(tmp < -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 順で一直線上
}

inline 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;
}

inline 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;
}

inline 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;
}

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

inline 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;
}

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

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

inline 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);
}

inline double dist(const line& l, const point& p) {
	return abs(cross((l.b - l.a), (p - l.a))) / abs(l.b - l.a);
}

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

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

inline double dist(const segment& s, const point& p) {
	if(dot((s.b - s.a), (p - s.a)) < 0) return abs(p - s.a);
	if(dot((s.a - s.b), (p - s.b)) < 0) return abs(p - s.b);
	return dist(line(s.a, s.b), p);
}

inline 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)));
}

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

inline bool intersect(const circle& c, const segment& s) {
	return dist(s, c.c) < c.r + EPS;
}

inline 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 m.a + (m.b - m.a) * cross(l.b - l.a, l.a - m.a) * (1.0 / tmp);
}

inline 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 t.a + (t.b - t.a) * cross(s.b - s.a, s.b - t.a) * (1.0 / tmp);
}

//先に，intersectを用いて交差判定を行うこと
inline 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;
}

inline 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;
}

inline 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;
}

inline double areaTriangle(point a, point b, const point& c) {
	a = a - c;
	b = b - c;
	return fabs(a.X * b.Y - b.X * a.Y) / 2.0;
}

inline double area(const polygon& p) {
	const int num = p.size();
	if(num < 3)
		return 0;

	if(num == 3)
		return areaTriangle(p[0], p[1], p[2]);

	double res = cross(p[num - 1], p[0]);
	for(int i = 1; i < num; ++i)
		res += cross(p[i - 1], p[i]);

	return abs(res) * 0.5;
}

// L.aからL.bの方向を見た場合に，点aが左側に来る．
inline line bisector(const point& a, const point& b) {
	return line(point((a.X - a.Y + b.X + b.Y) / 2.0, (a.Y + a.X + b.Y - b.X) / 2.0),
				point((a.X + a.Y + b.X - b.Y) / 2.0, (a.Y - a.X + b.Y + b.X) / 2.0));
}

// 点集合 pointsの凸包を求める．
inline polygon convex_hull(vector<point> points) {
	const int n = points.size();
	if(n <= 3)
		return points;

	sort(points.begin(), points.end());
	int k = 0;
	polygon res;
	res.resize(2 * n);
	for(int i = 0; i < n; res[k++] = points[i++])
		while(k >= 2 && ccw(res[k - 2], res[k - 1], points[i]) <= 0)
			--k;

	const int t = k + 1;
	for(int i = n - 2; i >= 0; res[k++] = points[i--])
		while(k >= t && ccw(res[k - 2], res[k - 1], points[i]) <= 0)
			--k;

	res.resize(k - 1);
	return res;
}
// L.aからL.bを向いた時の左側を残して切断する．
inline polygon convex_cut(const polygon& p, const line& l) {
	const int num = p.size();
	polygon res;
	for(int i = 0; i < num; ++i) {
		const int next = (i + 1) % num;
		const int tmp = ccw(l.a, l.b, p[i]);
		if(tmp != -1)
			res.push_back(p[i]);

		if(tmp * ccw(l.a, l.b, p[next]) < 0)
			res.push_back(crosspoint(l, line(p[i], p[next])));
	}

	return res;
}

vector<point> tangent(const circle& c, const point& p) {
	const double x = norm(p - c.c);
	double d = x - c.r * c.r;
	if(d < -EPS) return vector<point>();
	d = max(d, 0.0);
	const point q1 = (p - c.c) * (c.r * c.r / x);
	const point q2 = rotate90((p - c.c) * (-c.r * sqrt(d) / x));
	vector<point> res;
	res.push_back(c.c + q1 - q2);
	res.push_back(c.c + q1 + q2);
	return res;
}

vector<line> tangent(const circle &a, const circle& b) {
	vector<line> res;
	if(abs(a.r - b.r) < EPS) {
		point dir = b.c - a.c;
		dir = rotate90(dir * (a.r / abs(dir)));
		res.push_back(line(a.c + dir, b.c + dir));
		res.push_back(line(a.c - dir, b.c - dir));
	}
	else {
		point p = a.c * (-b.r) + b.c * a.r;
		p = p * (1.0 / (a.r - b.r));
		vector<point> ps = tangent(a, p), qs = tangent(b, p);
		for(int i = 0; i < min<int>(ps.size(), qs.size()); ++i)
			res.push_back(line(ps[i], qs[i]));
	}

	point p = a.c * b.r + b.c * a.r;
	p = p * (1.0 / (a.r + b.r));
	vector<point> ps = tangent(a, p), qs = tangent(b, p);
	for(int i = 0; i < min<int>(ps.size(), qs.size()); ++i)
		res.push_back(line(ps[i], qs[i]));

	return res;
}

// 三角形と点の包含関係，境界は含まない．
// 含める場合は == -1を <= 0とする．
bool contain_triangle(const polygon& triangle, const point& p) {
	const int d1 = ccw(p, triangle[0], triangle[1]), d2 = ccw(p, triangle[1], triangle[2]), d3 = ccw(p, triangle[2], triangle[0]);
	return !(d1 * d2 == -1 || d2 * d3 == -1 || d3 * d1 == -1);
}

// 多角形と点の包含関係．境界を含む．
bool contain(const polygon& P, const point& p) {
	const int n = P.size();
	bool res = false;
	for(int i = 0; i < n; ++i) {
		point v1 = P[i] - p, v2 = P[(i + 1) % n] - p;
		if(v1.Y > v2.Y)
			swap(v1, v2);

		if(v1.Y < EPS && EPS < v2.Y && cross(v1, v2) > EPS)
			res = !res;

		if(abs(cross(v1, v2)) < EPS && dot(v1, v2) < EPS)
			return true; // 境界を含まないなら，falseにする．
	}

	return res;
}

int n;
int start, goal;

struct edge{
	int to;
	double cost;
};

const double INF = 1e100;
const int MAX = 300;
vector<edge> G[MAX];

typedef pair<double, int> pdi;
double d[MAX];
bool connect[MAX][MAX];

class node {
public:
	int v;
	node() {}
	node(int v):v(v) {}

	bool operator<(const node &r) const {
		return d[v] > d[r.v];
	}
};

vector< pair<point, pii> > ps;

double dijkstra()
{
	fill(d, d+MAX, INF);
	priority_queue<node> que;

	d[start] = 0;
	que.push(node(start));
	while (!que.empty()) {
		node n = que.top(); que.pop();
		if (n.v == goal)
			break;
		rep(i, G[n.v].size()) {
			edge e = G[n.v][i];
			double c = d[n.v] + e.cost;
			if (d[e.to] > c) {
				d[e.to] = c;
				que.push(node(e.to));
			}
		}
	}

	return d[goal];
}

int main()
{
	while (cin >> n, n) {
		vector<circle> cs;
		ps.clear();

		rep(i, n) {
			int x, y, r;
			cin >> x >> y >> r;
			cs.push_back(circle(point(x, y), r));
		}

		ps.push_back(make_pair(cs[0].c, pii(0, 0)));
		for (int i = 1; i < cs.size(); i++) {
			if (intersect(cs[i-1], cs[i])) {
				vector<point> buf = crosspoint(cs[i-1], cs[i]);
				rep (j, 2)
					ps.push_back(make_pair(buf[j], pii(i-1, i)));
			}
		}
		{
			int t = cs.size()-1;
			ps.push_back(make_pair(cs[t].c, pii(t, t)));
		}

		int sz = ps.size();
		rep(i, sz) {
			REP(j, i+1, sz) {
				int lb = ps[i].second.second;
				int ub = ps[j].second.first;
				bool f = true;
				segment s = segment(ps[i].first, ps[j].first);
				for (int k = lb+1; k <= ub; k++) {
					vector<point> buf = crosspoint(cs[k-1], cs[k]);
					segment t = segment(buf[0], buf[1]);
					if (!intersect(s, t))
						f = false;
				}
				connect[i][j] = f;
				connect[j][i] = f;
			}
		}

		rep(i, sz) {
			vector<edge> e;
			rep(j, sz) {
				if (j == i) continue;
				if (connect[i][j]) {
					double d = dist(ps[i].first, ps[j].first);
					e.push_back( (edge){ j, d } );
				}
			}
			G[i] = e;
		}

		start = 0;
		goal = sz-1;
		printf("%.20lf\n", dijkstra());
	}
	return 0;
}