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:
// Chain-Confined Path

// 円同士の交点を頂点, 円内部を通る線分を辺としたダイクストラ

#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<cstdio>
#include<cfloat>
using namespace std;

typedef double Weight;
const double INF = DBL_MAX;
class Edge {
public:
    int source, target;
    Weight weight;
    Edge(int s, int t, Weight w) :source(s), target(t), weight(w) {}
    bool operator<(const Edge& e) const {
        if(weight != e.weight) return weight > e.weight;    // !!INVERSE!!
        return source != e.source ? source < e.source : target < e.target;
    }
};
class Graph {
public:
    vector< vector<Edge> > list;
    int size;
    Graph(int n) :size(n), list(vector< vector<Edge> >(n, vector<Edge>())) {};
    Weight Dijkstra(int, int) const;
};
Weight Graph::Dijkstra(int from, int to) const {
    vector<Weight> distance(size, INF);
    distance[from] = 0;
    priority_queue<Edge> q;
    q.push(Edge(from, from, 0));
    while(!q.empty()) {
        Edge now = q.top(); q.pop();
        int u = now.target;
        if(distance[u] == INF) break;
        for(vector<Edge>::const_iterator next = list[u].begin(); next != list[u].end(); next++) {
            int v = next->target;
            if(distance[v] <= distance[u] + next->weight) continue;
            distance[v] = distance[u] + next->weight;
            q.push(Edge(u, v, distance[v]));
        }
    }
    return distance[to];
}

const double EPS = 0.0;
// class
class Point;
class Segment;
class Line;
class Circle;
// member
class Point {
public:
    double x, y;
    Point(double a = 0.0, double b = 0.0) :x(a), y(b) {};
    bool operator== (const Point&) const;
    bool operator< (const Point&) const;
    bool operator> (const Point&) const;
    bool operator<= (const Point&) const;
    bool operator>= (const Point&) const;
    Point operator+(const Point&) const;
    Point operator-(const Point&) const;
    Point operator-() const;
    Point times(double) const;
    Point& operator=(const Point&);
    Point& operator+=(const Point&);
    Point& operator-=(const Point&);
    double dot(const Point&) const;
    double cross(const Point&) const;
    double abs() const;
    double norm() const;
    double distance(const Point&) const;
    double distance(const Segment&) const;
    double distance(const Line&) const;
    bool intersect(const Point&) const;
    bool intersect(const Segment&) const;
    bool intersect(const Line&) const;
    Point projection(const Line&) const;
    Point reflection(const Line&) const;
    int ccw(const Point&, const Point&) const;              // a.ccw(b, p)で3点a, b, pの位置関係を返す
                                                            //   0: a-p-b, 2: p-a-b, -2: a-b-p, 1: -a-b-の上にp, -1: -a-b-の下にp
};
class Segment {
public:
    Point source, target;
    Segment(Point a = Point(), Point b = Point()) :source(a), target(b) {};
    Line line() const;
    double distance(const Point&) const;
    double distance(const Segment&) const;
    double distance(const Line&) const;
    bool intersect(const Point&) const;
    bool intersect(const Segment&) const;
    bool intersect(const Line&) const;
};
class Line {
public:
    Point source, target;
    Line(Point a = Point(), Point b = Point()) :source(a), target(b) {};
    Segment segment() const;
    double distance(const Point&) const;
    double distance(const Segment&) const;
    double distance(const Line&) const;
    bool intersect(const Point&) const;
    bool intersect(const Segment&) const;
    bool intersect(const Line&) const;
    Point projection(const Point&) const;
    Point reflection(const Point&) const;
    Point crosspoint(const Line&) const;
};
class Circle {
public:
    double x, y, r;
    Circle(double a = 0.0, double b = 0.0, double c = 0.0) :x(a), y(b), r(c) {};
    Point point() const;
    double distance(const Point&) const;                    // 円の中心と点の距離
    double distance(const Circle&) const;                   // 円の中心同士の距離
    bool include(const Point&) const;                       // 点を含むか
    bool include(const Circle&) const;                      // 円を含むか
    bool intersect(const Circle&) const;
    vector<Point> crosspoint(const Circle&) const;
};
// Point
bool Point::operator== (const Point &p) const {return x == p.x && y == p.y;}
bool Point::operator<(const Point &p) const {return x != p.x ? x < p.x : y < p.y;}
bool Point::operator>(const Point &p) const {return x != p.x ? x > p.x : y > p.y;}
bool Point::operator<=(const Point &p) const {return x != p.x ? x < p.x : y <= p.y;}
bool Point::operator>=(const Point &p) const {return x != p.x ? x > p.x : y >= p.y;}
Point Point::operator+(const Point& p) const {return Point(x + p.x, y + p.y);}
Point Point::operator-(const Point& p) const {return Point(x - p.x, y - p.y);}
Point Point::operator-() const {return Point(-x, -y);}
Point Point::times(double d) const {return Point(x * d, y * d);}
Point& Point::operator=(const Point& p) {x = p.x; y = p.y; return *this;}
Point& Point::operator+=(const Point& p) {x += p.x; y += p.y; return *this;}
Point& Point::operator-=(const Point& p) {x -= p.x; y -= p.y; return *this;}
double Point::dot(const Point& p) const {return x * p.x + y * p.y;}
double Point::cross(const Point& p) const {return x * p.y - y * p.x;}
double Point::abs() const {return hypot(x, y);}
double Point::norm() const {return x * x + y * y;}
double Point::distance(const Point& p) const {return (p - (*this)).abs();}
double Point::distance(const Segment& s) const {return s.distance(*this);}
double Point::distance(const Line& l) const {return l.distance(*this);}
bool Point::intersect(const Point& p) const {return *this == p;}
bool Point::intersect(const Segment& s) const {return s.intersect(*this);}
bool Point::intersect(const Line& l) const {return l.intersect(*this);}
Point Point::projection(const Line& l) const {return l.projection(*this);}
Point Point::reflection(const Line& l) const {return l.reflection(*this);}
int Point::ccw(const Point& b, const Point& p) const {
    const Point& a = *this;
    Point v1 = b - a;
    Point v2 = p - a;
    if(v1.cross(v2) > 0.0) return 1;
    if(v1.cross(v2) < 0.0) return -1;
    if(v1.dot(v2) < 0.0) return 2;
    if(v1.norm() < v2.norm()) return -2;
    return 0;
}
// Segment
Line Segment::line() const {return Line(source, target);}
double Segment::distance(const Point& p) const {
    Point q = line().projection(p);
    if(intersect(q)) return q.distance(p);
    double a = source.distance(p);
    double b = target.distance(p);
    return a < b ? a : b;
}
double Segment::distance(const Segment& s) const {
    if(intersect(s)) return 0.0;
    double a = distance(s.source);
    double b = distance(s.target);
    double c = s.distance(source);
    double d = s.distance(target);
    a = a < b ? a : b;
    a = a < c ? a : c;
    return a < d ? a : d;
}
double Segment::distance(const Line& l) const {return l.distance(*this);}
bool Segment::intersect(const Point& p) const {
    return source.distance(p) + target.distance(p) - target.distance(source) <= EPS;
}
bool Segment::intersect(const Segment& s) const {
    bool a = s.source.ccw(s.target, source) * s.source.ccw(s.target, target) <= EPS;
    bool b = source.ccw(target, s.source) * source.ccw(target, s.target) <= EPS;
    return a && b;
}
bool Segment::intersect(const Line& l) const {return l.intersect(*this);}
// Line
Segment Line::segment() const {return Segment(source, target);}
double Line::distance(const Point& p) const {return p.distance(projection(p));}
double Line::distance(const Segment& s) const {
    if(intersect(s)) return 0.0;
    double a = distance(s.source);
    double b = distance(s.target);
    return a < b ? a : b;
}
double Line::distance(const Line& l) const {return intersect(l) ? 0.0 : distance(l.source);}
bool Line::intersect(const Point& p) const {
    Point v1 = source - p;
    Point v2 = target - p;
    return fabs(v2.cross(v1)) < EPS;
}
bool Line::intersect(const Segment& s) const {
    Point v1 = target - source;
    Point v2 = s.source - source;
    Point v3 = s.target - source;
    return v1.cross(v2) * v1.cross(v3) <= EPS;
}
bool Line::intersect(const Line& l) const {
    Point v1 = target - source;
    Point v2 = l.target - l.source;
    Point v3 = l.source - source;
    return fabs(v1.cross(v2)) > EPS || fabs(v1.cross(v3)) < EPS;
}
Point Line::projection(const Point& p) const {
    Point v1 = p - source;
    Point v2 = source - target;
    return Point(source + v2.times(v1.dot(v2) / v2.norm()));
}
Point Line::reflection(const Point& p) const {
    return p + (projection(p) - p).times(2.0);
}
Point Line::crosspoint(const Line& l) const {
    Point v1 = target - source;
    Point v2 = l.target - l.source;
    Point v3 = target - l.source;
    double a = v1.cross(v2);
    double b = v1.cross(v3);
    if(fabs(a) <= EPS && fabs(b) <= EPS) l.source;
    return l.source + v2.times(b / a);
}
// Circle
Point Circle::point() const {return Point(x, y);}
double Circle::distance(const Point& p) const {return point().distance(p);}
double Circle::distance(const Circle& c) const {return point().distance(c.point());}
bool Circle::include(const Point& p) const {return distance(p) - r <= EPS;}
bool Circle::include(const Circle& c) const {return distance(c) - (r - c.r) <= EPS;}
bool Circle::intersect(const Circle& c) const {return distance(c) - r - c.r <= EPS;}
vector<Point> Circle::crosspoint(const Circle& c) const {
    double angle = atan2(c.y - y, c.x - x);
    double d = distance(c);
    double add = acos((d * d + r * r - c.r * c.r) / (2.0 * d * r));
    vector<Point> result;
    result.push_back(Point(x + r * cos(angle + add), y + r * sin(angle + add)));
    result.push_back(Point(x + r * cos(angle - add), y + r * sin(angle - add)));
    return result;
}

int main() {
    int n;
    while(cin>>n, n) {
        vector<Circle> circle(n);
        for(int i = 0; i < n; i++) {
            double x, y, r;
            cin>>x>>y>>r;
            circle[i] = Circle(x, y, r);
        }
        vector<Segment> gate;
        vector<Point> vertex;
        vertex.push_back((*circle.begin()).point());
        for(int i = 0; i < n - 1; i++) {
            vector<Point> p = circle[i].crosspoint(circle[i + 1]);
            gate.push_back(Segment(p[0], p[1]));
            vertex.insert(vertex.end(), p.begin(), p.end());
        }
        vertex.push_back((*circle.rbegin()).point());
        Graph g(vertex.size());
        for(int i = 0; i < vertex.size() - 1; i++) {
            for(int j = i + 1; j < vertex.size(); j++) {
                Segment edge(vertex[i], vertex[j]);
                int firstGate = (i + 1) / 2;
                int lastGate = (j + 1) / 2 - 1;
                if(j == vertex.size() - 1) lastGate--;
                bool ok = true;
                for(int k = firstGate; k <= lastGate; k++) {
                    if(!edge.intersect(gate[k])) ok = false;
                }
                if(ok) (g.list[i]).push_back(Edge(i, j, vertex[i].distance(vertex[j])));
            }
        }
        printf("%.6f\n", g.Dijkstra(0, vertex.size() - 1));
//         for(int i=0; i<(g.list).size(); i++) {cout<<vertex[i].x<<", "<<vertex[i].y<<endl;}
//         for(int i=0; i<(g.list).size(); i++) {
//             for(int j=0; j<(g.list[i]).size(); j++) {
//                 cout<<" "<<((g.list[i])[j]).target<<":"<<((g.list[i])[j]).weight;
//             }
//             cout<<endl;
//         }
//         return(1);
//         cout<<g.Dijkstra(0, vertex.size() - 1)<<endl;
    }
}