// 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++) {
                Line 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;
    }
}

Measured memory_bytes: 1476