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 JAVA):

Solution:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	
	
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);

		while (true) {
			final int n = sc.nextInt();
			
			if(n == 0){
				break;
			}
			
			Point2D[] circle = new Point2D[n];
			int[] circle_r = new int[n];
			
			for(int i = 0; i < n; i++){
				circle[i] = new Point2D(sc.nextInt(), sc.nextInt());
				circle_r[i] = sc.nextInt();
			}
			
			Point2D[] points = new Point2D[n * 2];
			
			points[0] = new Point2D(circle[0].x, circle[0].y);
			
			for(int num = 0; num < n - 1; num++){
				Point2D[] result = Point2D.cross_ss(circle[num], circle_r[num], circle[num+1], circle_r[num+1]);
				points[2 * num + 1] = result[0];
				points[2 * num + 2] = result[1];
			}
			
			points[2*n-1] = new Point2D(circle[n-1].x, circle[n-1].y);
			
			double[][] adj = new double[n * 2][n * 2];
			for(int i = 0; i < n * 2; i++){
				Arrays.fill(adj[i], Double.MAX_VALUE);
			}
			
			for(int from = 0; from < 2 * n; from++){
				for(int to = from + 1; to < 2 * n; to++){
					final int start = Math.min(n - 2, (from - 1) / 2);
					final int end = Math.min(n - 2, (to - 1) / 2);
					
					//System.out.println(from + " " + start + " " + to + " " + end + " : " + n);
					
					boolean flag = true;
					for(int line = start; line <= end; line++){
						final int s_line = line * 2 + 1;
						final int e_line = line * 2 + 2;
						
						//System.out.println(s_line + " " + e_line);
						
						if(!Point2D.intersect_s(points[from], points[to], points[s_line], points[e_line])){
							flag = false;
							break;
						}
					}
					
					if(flag){
						adj[from][to] = adj[to][from] = points[from].dist(points[to]);
						//System.out.println(from + " " + to + " =>" + adj[from][to]);
					}
				}
			}
			
			double[] dist = new double[n * 2];
			boolean[] used = new boolean[n * 2];
			Arrays.fill(dist, Double.MAX_VALUE);
			dist[0] = 0;
			
			for(int tt = 0; tt < 2 * n; tt++){
				int min_pos = -1;
				double min = Double.MAX_VALUE;
				
				//System.out.println(tt + Arrays.toString(dist));
				
				for(int pos = 0; pos < 2 * n; pos++){
					if(!used[pos] && dist[pos] < min){
						min = dist[pos];
						min_pos = pos;
					}
				}
				
				used[min_pos] = true;
				if(min_pos == 2 * n - 1){
					break;
				}
				
				for(int to = 0; to < 2 * n; to++){
					if(used[to] || adj[min_pos][to] == Double.MAX_VALUE){
						continue;
					}
					
					dist[to] = Math.min(dist[to], dist[min_pos] + adj[min_pos][to]);
				}
			}
			
			System.out.printf("%.6f\n", dist[2 * n - 1]);
		}
	}
	
	public static class Point2D{
		public double x;
		public double y;

		public static final double EPS = 1e-9;

		public Point2D(double x, double y) {
			this.x = x;
			this.y = y;
		}
		
		//オマケ
		public Point2D(Point2D point) {
			this.x = point.x;
			this.y = point.y;
		}

		//オマケ
		public String toString() {
			return x + "," + y;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof Point2D) {
				Point2D another = (Point2D) o;
				
				if(Point2D.eq(this.x, another.x) && Point2D.eq(this.y, another.y)){
					return true;
				}
				
				return false;
			}
			return false;
		}
		
		public Point2D add(Point2D another) {
			Point2D ret = new Point2D(this);
			ret.x += another.x;
			ret.y += another.y;
			return ret;
		}
		
		public Point2D minus(){
			Point2D ret = new Point2D(this);
			ret.x = -ret.x;
			ret.y = -ret.y;
			return ret;
		}
		
		public Point2D sub(Point2D another) {
			return this.add(another.minus());
		}

		public Point2D mul(double d) {
			Point2D ret = new Point2D(this);
			ret.x *= d;
			ret.y *= d;
			return ret;
		}

		public Point2D div(double d) {
			Point2D ret = new Point2D(this);
			ret.x /= d;
			ret.y /= d;
			return ret;
		}
		
		public double dot(Point2D another) {
			return this.x * another.x + this.y * another.y;
		}

		public double cross(double x, double y) {
			return this.x * y - this.y * x;
		}

		public double cross(Point2D another) {
			return this.x * another.y - this.y * another.x;
		}
		
		public double dist(Point2D another){
			return Math.sqrt((this.x - another.x) * (this.x - another.x) +
					 		 (this.y - another.y) * (this.y - another.y));
		}

		public double dist_o() {
			final Point2D ZERO = new Point2D(0, 0);
			return this.dist(ZERO);
		}

		public Point2D unit() {
			return this.div(this.dist_o());
		}

		public boolean pol(Point2D start, Point2D end) {
			return end.sub(start).cross(this.sub(start)) < EPS;
		}

		public boolean pos(Point2D start, Point2D end) {
			return (start.dist(this) + this.dist(end) < start.dist(end) + EPS);
		}

		public double pld(Point2D start, Point2D end) {
			return Math.abs((end.sub(start).cross(this.sub(start)))
					/ end.sub(start).dist_o());
		}

		public double psd(Point2D start, Point2D end) {
			if (end.sub(start).dot(this.sub(start)) < EPS) {
				return this.dist(start);
			} else if (start.sub(end).dot(this.sub(end)) < EPS) {
				return this.dist(end);
			} else {
				return Math.abs(end.sub(start).cross(this.sub(start)) / end.dist(start));
			}
		}
		
		public static int signum(double x){
			return Math.abs(x) < EPS ? 0 : x > 0 ? 1 : -1;
		}
		
		public static boolean eq(double x, double y){
			return signum(x - y) == 0;
		}
		
		public static int ccw(Point2D p, Point2D r, Point2D s){
			Point2D a = r.sub(p);
			Point2D b = s.sub(p);
			
			final int sgn = Point2D.signum(a.cross(b));
			if(sgn != 0){
				return sgn;
			}else if(a.x * b.x < -EPS && a.y * b.y < -EPS){
				return -1;
			}else if(a.dist_o() < b.dist_o() - EPS){
				return 1;
			}else{
				return 0;
			}
		}
		
		public static boolean intersect_s(Point2D a1, Point2D a2, Point2D b1,
				Point2D b2) {
			return (Point2D.ccw(a1, a2, b1) * Point2D.ccw(a1, a2, b2) <= 0)
					&& (Point2D.ccw(b1, b2, a1) * Point2D.ccw(b1, b2, a2) <= 0);
		}

		public static boolean insersect_l(Point2D a1, Point2D a2, Point2D b1,
				Point2D b2) {
			return a1.sub(a2).cross(b1.sub(b2)) < EPS;
		}

		public static Point2D interpoint_s(Point2D a1, Point2D a2, Point2D b1,
				Point2D b2) {
			Point2D b = b2.sub(b1);
			double d1 = Math.abs(b.cross(a1.sub(b1)));
			double d2 = Math.abs(b.cross(a2.sub(b1)));
			double t = d1 / (d1 + d2);
			Point2D a = a2.sub(a1), v = a.mul(t);
			return a1.add(v);
		}

		public static Point2D interpoint_l(Point2D a1, Point2D a2, Point2D b1,
				Point2D b2) {
			Point2D a = a2.sub(a1);
			Point2D b = b2.sub(b1);
			double t = b.cross(b1.sub(a1)) / b.cross(a);
			Point2D v = a.mul(t);
			return a1.add(v);
		}

		public static Point2D[] cross_ss(Point2D p1, double r1, Point2D p2,
				double r2) {
			double dis = p1.dist(p2);

			if (r1 + EPS > r2 && r1 - EPS < r2 && dis < EPS) {
				return new Point2D[0]; // same
			}

			if (dis - EPS < r1 + r2 && dis + EPS > r1 + r2) {
				Point2D tmp = p2.sub(p1);
				tmp = tmp.mul(r1 / tmp.dist_o());
				Point2D ret[] = new Point2D[1];
				ret[0] = p1.add(tmp);
				return ret;
			} else if (dis + EPS > r1 + r2) {
				return new Point2D[0]; // out
			}

			double dis_m = Math.abs(r1 - r2);

			if (dis_m + EPS > dis && dis_m - EPS < dis) {
				Point2D tmp = null;
				if (r1 > r2) {
					tmp = p2.sub(p1);
				} else {
					tmp = p1.sub(p2);
				}

				double min = Math.min(r1, r2);

				tmp = tmp.mul((min + tmp.dist_o()) / tmp.dist_o());

				Point2D ret[] = new Point2D[1];
				ret[0] = p1.add(tmp);
				return ret;
			} else if (dis_m + EPS > dis) {
				return new Point2D[0]; // inner
			} else {
				Point2D ret[] = new Point2D[2];

				double theta = Math.acos((dis * dis + r1 * r1 - r2 * r2)
						/ (2 * dis * r1));
				double a = Math.atan2(p2.y - p1.y, p2.x - p1.x);

				ret[0] = new Point2D(r1 * Math.cos(a + theta) + p1.x, r1
						* Math.sin(a + theta) + p1.y);
				ret[1] = new Point2D(r1 * Math.cos(a - theta) + p1.x, r1
						* Math.sin(a - theta) + p1.y);
				return ret;
			}
		}
		
		public static double ss_dist(Point2D start1, Point2D end1, Point2D start2, Point2D end2){
			if(Point2D.intersect_s(start1, end1, start2, end2)){
				return 0;
			}else{
				return Math.min(Math.min(Math.min(start1.psd(start2, end2), end1.psd(start2, end2)), start2.psd(start1, end1)), end2.psd(start1, end1));
			}
		}
		
		public void interpoint_lc(Point2D start, Point2D end, Point2D c, double r,
				Point2D ans[]) {
			if (c.pld(start, end) > r + EPS)
				return;
			Point2D v = end.sub(start).unit();
			double delta = v.dot(start.sub(c)) * v.dot(start.sub(c))
					- start.dist(c) * start.dist(c) + r * r;
			double t = -v.dot(start.sub(c));
			double s = Math.sqrt(delta);
			ans[0] = start.add(v.mul(t + s));
			ans[1] = start.add(v.mul(t + s));
		}

		public Point2D normal_vector(Point2D p, Point2D a, Point2D b) {
			Point2D v = b.sub(a).unit();
			v = v.cross(p.sub(a)) > 0 ? new Point2D(v.y, (-1) * v.x) : new Point2D(
					(-1) * v.y, v.x);
			return v.mul(p.pld(a, b));
		}

		public double area(Point2D a, Point2D b, Point2D c) {
			return Math.abs((c.sub(a).cross(b.sub(a))) * 0.5);
		}
	}

}