#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


// http://is2011.2-d.jp/moin/moin.cgi/amylase/icpc#A.2BdvR92jBuTqRwuQ-

#define rep(i,n) for(int i=0;i<n;++i)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define F first
#define S second
#define SZ(a) (int)((a).size())
// primitives
typedef double Real;
typedef complex<Real> Point;
typedef pair<Point, Point> Line;
typedef pair<Point, Real> Circle;
typedef vector<Point> Poly;

Real eps = 1e-9;

vector<Point> CCintersect (Circle c, Circle d) {
    vector<Point> ret;
    const Real dist = abs(c.first - d.first);
    const Real cr = c.second;
    const Real dr = d.second;

    if (dist > cr + dr) return ret;
    if (dist < abs(cr - dr)) return ret;

    const Real s = (cr + dr + dist) / 2.;
    const Real area = sqrt(s * (s - cr) * (s - dr) * (s - dist));
    const Real h = 2 * area / dist;

    Point v = d.first - c.first; v /= abs(v);
    const Point m = c.first + sqrt(cr * cr - h * h) * v;
    const Point n = v * Point(0, 1);

    ret.push_back(m + n * h);
    ret.push_back(m - n * h);
    return ret;
}

inline Real dot(const Point& p, const Point& q){return p.real() * q.real() + p.imag() * q.imag();}
inline Real cross(const Point& p, const Point& q){return p.real() * q.imag() - p.imag() * q.real();}

// ccw_b : old version of ccw.
inline Real ccw_b(const Point& p, const Point& q, const Point& r) {return cross(q - p, r - p);}

/* ccw :
CD  : counter direction
CW  : clock wise
OS  : on segment
CCW : counter clock wise
D   : direction
 */
enum LPposit { P_CD = -2, P_CW = -1, P_OS = 0, P_CCW = 1, P_D = 2};
LPposit ccw(const Point& p, const Point& q, const Point& r) {
  Real c = ccw_b(p, q, r);
  if (c < -eps) return P_CW;
  if (c >  eps) return P_CCW;
  if (dot(q - p, r - p) < -eps) return P_CD;
  if (dot(p - q, r - q) < -eps) return P_D;
  return P_OS;
}

bool crossS(const Line& p, const Line& q){
  return
    ccw(p.first, p.second, q.first) * ccw(p.first, p.second, q.second) <= 0 &&
    ccw(q.first, q.second, p.first) * ccw(q.first, q.second, p.second) <= 0;
}

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);

    int n;
    while(cin>>n){
        if(n==0) break;
        double x[n],y[n],r[n];
        Circle c[n];
        for(int i=0;i<n;i++){
            cin>>x[i]>>y[i]>>r[i];
            c[i] = {{x[i],y[i]},r[i]};
        }
        Point p[2*n]={};
        p[0]={x[0],y[0]};
        p[2*n-1] = {x[n-1],y[n-1]};
        for(int i=0;i<n-1;i++){
            vector<Point> ret = CCintersect(c[i],c[i+1]);
            if(imag(ret[0]) < imag(ret[1])) swap(ret[0],ret[1]);
            p[2*i+1] = {ret[0]};
            p[2*i+2] = {ret[1]};
        }
        int m = 2*n;
        double dp[m][m]={};
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                if(i!=j) dp[i][j] = 1e9;
            }
        }
        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                bool pos = true;
                int next, last;
                if(i%2) next = i+2;
                else next = i+1;
                if(j%2) last = j-2;
                else last = j-3;
                for(int k=next;k<=last;k+=2){
                    //k,k+1と交差しているか
                    Line y1 = {p[i],p[j]}, y2 = {p[k],p[k+1]};
                    bool ok = crossS(y1,y2);
                    if(!ok){
                        pos = false;
                        break;
                    }
                }
                if(pos){
                    dp[i][j] = abs(p[i] - p[j]);
                    dp[j][i] = dp[i][j];
                }
            }
        }

        for(int k=0;k<m;k++)for(int i=0;i<m;i++)for(int j=0;j<m;j++){
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
        }
        cout << dp[0][m-1] << "\n";


    }
}


Measured memory_bytes: 3644