#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define FOR(i,k,n) for(int i=(k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
 
const double INF = 1e8;
const double EPS = 1e-8;
 
#include <complex>
#define CURR(P, i) (P[(i) % P.size()])
#define NEXT(P, i) (P[((i) + 1) % P.size()])
 
 
typedef complex<double> Point;
typedef vector<Point> Polygon;
struct Line : public vector<Point> {
    Line() {;}
    Line(Point a, Point b) { push_back(a); push_back(b); }
};
struct Circle {
    Point p;
    double r;
    Circle() {;}
    Circle(Point p, double r) : p(p), r(r) {;}
};
inline double cross(const Point &a, const Point &b) {
      return imag(conj(a) * b);
}
inline double dot(const Point &a, const Point &b) {
      return real(conj(a) * b);
}
Point projection(const Line &l, const Point &p) {
    double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
    return l[0] + t * (l[0] - l[1]);
}
inline int ccw(Point a, Point b, Point c) {
    b -= a;
    c -= a;
    if (cross(b, c) > 0) { return 1; }
    if (cross(b, c) < 0) { return -1; }
    if (dot(b, c) < 0) { return 2; }
    if (norm(b) < norm(c)) { return -2; }
    return 0;
}
bool intersectSS(const Line &s, const Line &t) {
    return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
        ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}
vector<Point> crosspointLC(const Line &l, const Circle &c) {
    vector<Point> ret;
    Point center = projection(l, c.p);
    double d = abs(center - c.p);
    double t = sqrt(c.r * c.r - d * d);
    if (isnan(t)) { return ret; }
    Point vect = (l[1] - l[0]);
    vect /= abs(vect);
    ret.push_back(center - vect * t);
    if (t > EPS) {
        ret.push_back(center + vect * t);
    }
    return ret;
}
vector<Point> crosspointCC(const Circle &c1, const Circle &c2) {
    vector<Point> ret;
    double d = abs(c1.p - c2.p);
    if (max(c1.r, c2.r) - min(c1.r, c2.r) - d> -EPS) { return ret; }
    double x = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
    Point start = c1.p + (c2.p - c1.p) / d * x;
    Point vect = (c1.p - c2.p) * Point(0.0, 1.0);
    return crosspointLC(Line(start, start + vect), c1);
}
int main(){
    int N;
    while(cin>>N && N){
        Point p[100];
        double r[100];
        vector<Circle> circles;
        REP(i, N){
            double x, y;
            cin>>x>>y>>r[i];
            p[i] = Point(x, y);
            circles.push_back(Circle(p[i], r[i]));
        }
        double d[300][300];
        vector<Point> crosses;
        REP(i, N-1) {
            vector<Point> cv = crosspointCC(circles[i], circles[i+1]);
            crosses.push_back(cv[0]);
            crosses.push_back(cv[1]);
        }
        const int S = 2 * (N - 1);
        const int G = S + 1;
        const int SIZE = G + 1;
        REP(i, SIZE)REP(j, SIZE) d[i][j] = INF;
        REP(i, crosses.size())FOR(j, i+1, crosses.size()){
            Line line(crosses[i], crosses[j]);
            int idx1 = i / 2 + 1, idx2 = j /2;
            bool ok = true;
            for(int k = idx1; k < idx2; k++){
                Line t(crosses[2*k], crosses[2*k+1]);
                if(!intersectSS(line, t)) ok = false;
            }
            if(!ok) continue;
            //printf("ok %d %d %f\n", i, j, abs(crosses[i] - crosses[j]));
            d[i][j] = d[j][i] = abs(crosses[i] - crosses[j]);
        }
        REP(j, crosses.size()){
            int i = S;
            Line line(p[0], crosses[j]);
            bool ok = true;
            int idx1 = 0, idx2 = j / 2;
            for(int k = idx1; k < idx2; k++){
                Line t(crosses[2*k], crosses[2*k+1]);
                if(!intersectSS(line, t)) ok = false;
            }
            if(!ok) continue;
            //printf("ok %d %d %f\n", i, j, abs(crosses[i] - crosses[j]));
            d[i][j] = d[j][i] = abs(crosses[j] - p[0]);
        }
        REP(i, crosses.size()){
            int j = G;
            Line line(crosses[i], p[N-1]);
            bool ok = true;
            int idx1 = i / 2 + 1, idx2 = N - 1;
            for(int k = idx1; k < idx2; k++){
                Line t(crosses[2*k], crosses[2*k+1]);
                if(!intersectSS(line, t)) ok = false;
            }
            if(!ok) continue;
            //printf("ok %d %d %f\n", i, j, abs(crosses[i] - crosses[j]));
            d[i][j] = d[j][i] = abs(crosses[i] - p[N-1]);
        }
        {
            int i = S; int j = G;
            Line line(p[0], p[N-1]);
            bool ok = true;
            int idx1 = 0, idx2 = N - 1;
            for(int k = idx1; k < idx2; k++){
                Line t(crosses[2*k], crosses[2*k+1]);
                if(!intersectSS(line, t)) ok = false;
            }
            //printf("ok %d %d %f\n", i, j, abs(crosses[i] - crosses[j]));
            if(ok) d[i][j] = d[j][i] = abs(p[N-1] - p[0]);
        }
        REP(k, SIZE)REP(i, SIZE)REP(j, SIZE){
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        printf("%.8lf\n", d[S][G]);
    }
    return 0;
}


Measured memory_bytes: 3740