#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const double EPS = 1.0e-10;
const double INF = DBL_MAX / 1000;

class Point
{
public:
    double y, x;
    Point(){
        y = x = 0.0;
    }
    Point(double y0, double x0){
        y = y0;
        x = x0;
    }
    Point operator+(const Point& p) const{
        return Point(y + p.y, x + p.x);
    }
    Point operator-(const Point& p) const{
        return Point(y - p.y, x - p.x);
    }
    Point operator*(double a) const{
        return Point(y * a, x * a);
    }
    Point operator/(double a) const{
        return Point(y / a, x / a);
    }
    double length() const{
        return sqrt(y * y + x * x);
    }
    double dist(const Point& p) const{
        return sqrt(pow(y - p.y, 2) + pow(x - p.x, 2));
    }
    double dot(const Point& p) const{
        return y * p.y + x * p.x; // |a|*|b|*cos慮
    }
    double cross(const Point& p) const{
        return x * p.y - y * p.x; // |a|*|b|*sin慮
    }
};

void circlesIntersection(const Point& p1, double r1, const Point& p2, double r2, vector<Point>& intersection)
{
    double y = p2.y - p1.y;
    double x = p2.x - p1.x;
    double a = (y*y + x*x + r1*r1 - r2*r2) / 2;
    double b = (y*y + x*x) * r1*r1 - a*a;

    intersection.assign(2, Point(x, -y) * sqrt(b));
    intersection[1] = intersection[1] * -1;
    for(int i=0; i<2; ++i)
        intersection[i] = (intersection[i] + Point(y, x) * a) / (y*y + x*x) + p1;
}

bool segmentsCollide(const Point& a1, const Point& a2, const Point& b1, const Point& b2)
{
    if(min(a1.x, a2.x) > max(b1.x, b2.x) || min(b1.x, b2.x) > max(a1.x, a2.x) || min(a1.y, a2.y) > max(b1.y, b2.y) || min(b1.y, b2.y) > max(a1.y, a2.y))
        return false;

    return ((a2-a1).cross(b1-a1) * (a2-a1).cross(b2-a1) < EPS) && ((b2-b1).cross(a1-b1) * (b2-b1).cross(a2-b1) < EPS);
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<Point> p(n);
        vector<double> r(n);
        for(int i=0; i<n; ++i)
            cin >> p[i].x >> p[i].y >> r[i];

        vector<vector<Point> > intersection(n+1);
        for(int i=1; i<n; ++i)
            circlesIntersection(p[i], r[i], p[i-1], r[i-1], intersection[i]);
        intersection[0].assign(2, p[0]);
        intersection[n].assign(2, p[n-1]);

        vector<vector<double> > dp(n+1, vector<double>(2, INF));
        dp[0][0] = 0.0;
        for(int a=0; a<n+1; ++a){
            for(int b=0; b<2; ++b){
                for(int c=a+1; c<n+1; ++c){
                    for(int d=0; d<2; ++d){
                        bool ok = true;
                        for(int i=a+1; i<c; ++i){
                            if(!segmentsCollide(intersection[a][b], intersection[c][d], intersection[i][0], intersection[i][1]))
                                ok = false;
                        }
                        if(ok)
                            dp[c][d] = min(dp[c][d], dp[a][b] + intersection[a][b].dist(intersection[c][d]));
                    }
                }
            }
        }

        printf("%.10f\n", dp[n][0]);
    }
}

Measured memory_bytes: 1276