#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define all(v) (v).begin(),(v).end()

using namespace std;

typedef pair<double,int>P;
typedef complex<double> C;

struct edge
{
    int to;
    double cost;
};

const int MAX_N = 105;

C v[MAX_N];
int r[MAX_N];
vector<edge> G[2*MAX_N];
int n;
double d[2*MAX_N];

namespace std {
  bool operator < (const C& a, const C& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

double cross(const C& a, const C& b) {
  return imag(conj(a)*b);
}
double dot(const C& a, const C& b) {
  return real(conj(a)*b);
}

struct L : public vector<C> {
  L(const C &a, const C &b) {
    push_back(a); push_back(b);
  }
};

int ccw(C a, C b, C c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

bool intersectLL(const L &l, const L &m) {
  return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || // non-parallel
         abs(cross(l[1]-l[0], m[0]-l[0])) < EPS;   // same line
}
bool intersectLS(const L &l, const L &s) {
  return cross(l[1]-l[0], s[0]-l[0])*       // s[0] is left of l
         cross(l[1]-l[0], s[1]-l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const L &l, const C &p) {
  return abs(cross(l[1]-p, l[0]-p)) < EPS;
}
bool intersectSS(const L &s, const L &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;
}

L cross_line(C p1,int r1,C p2,int r2)
{
    double d = norm(p2-p1);
    double t = r2*r2 - r1*r1 - d;
    double aa = d,bb = t*(real(p2)-real(p1)),cc = t*t / 4.0 - (imag(p2) - imag(p1))*(imag(p2) - imag(p1))*r1*r1;
    double x1 = (-bb + sqrt(bb*bb - 4*aa*cc))/(2*aa);
    double x2 = (-bb - sqrt(bb*bb - 4*aa*cc))/(2*aa);
    double y1,y2;
    if(imag(p1) == imag(p2)){
        y1 = sqrt(r1*r1 - x1*x1);
        y2 = -y1;
    }else{
        y1 = (t+2*(real(p2)-real(p1))*x1)/(-2*(imag(p2)-imag(p1)));
        y2 = (t+2*(real(p2)-real(p1))*x2)/(-2*(imag(p2)-imag(p1)));
    }
    L ln = L(C(x1+real(p1),y1+imag(p1)),C(x2+real(p1),y2+imag(p1)));
    return ln;
}

void dijkstra(int s)
{
	priority_queue<P,vector<P>,greater<P> > que;
	d[s] = 0.0;
	que.push(P(0.0,s));
	while(!que.empty()){
		P p = que.top();
		que.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		vector<edge>::iterator it = G[v].begin();
		rep(i,G[v].size()){
			if(d[G[v][i].to] > d[v] + G[v][i].cost){
				d[G[v][i].to] = d[v] + G[v][i].cost;
				que.push(P(d[G[v][i].to],G[v][i].to));
			}
		}
	}
}

int main()
{
    while(1){
        scanf("%d",&n);
        if(n == 0){
            break;
        }
        rep(i,2*n){
            G[i].clear();
        }
    	rep(i,n){
            int bf1,bf2;
    		scanf("%d%d%d",&bf1,&bf2,&r[i]);
            v[i] = C(bf1,bf2);
    	}
        vector<L> vec;
        vector<L> sect;
        rep(i,n-1){
            vec.push_back(cross_line(v[i],r[i],v[i+1],r[i+1]));
        }
        bool fl = false;
        rep(k,n-1){
            if(!intersectSS(L(v[0],v[n-1]),vec[k])){
                fl =true;
                break;
            }
        }
        if(!fl){
            G[0].push_back((edge){2*n-1,abs(v[n-1] - v[0])});
        }
        rep(j,n-1){
            rep(id,2){
                bool flag = false;
                rep(k,j){
                    if(!intersectSS(L(v[0],vec[j][id]),vec[k])){
                        flag =true;
                        break;
                    }
                }
                if(!flag){
                    G[0].push_back((edge){2*j+1+id,abs(vec[j][id] - v[0])});
                }
            }
        }
        rep(i,n-2){
            for(int j=i+1;j<=n-2;j++){
                rep(id,2){
                    rep(id2,2){
                        bool flag = false;
                        for(int k = i+1;k < j;k++){
                            if(!intersectSS(L(vec[i][id],vec[j][id2]),vec[k])){
                                flag = true;
                                break;
                            }
                        }
                        if(!flag){
                            G[2*i+1+id].push_back((edge){2*j+1+id2,abs(vec[j][id2] - vec[i][id])});
                        }
                    }
                }
            }
        }
        rep(j,n-1){
            rep(id,2){
                bool flag = false;
                for(int k = j+1;k <= n-2;k++){
                    if(!intersectSS(L(v[n-1],vec[j][id]),vec[k])){
                        flag =true;
                        break;
                    }
                }
                if(!flag){
                    G[2*j+1+id].push_back((edge){2*n-1,abs(vec[j][id] - v[n-1])});
                }
            }
        }
        fill(d,d+n*2,INF);
        dijkstra(0);
        printf("%.6f\n",d[2*n-1]);
    }
	return 0;
}

Measured memory_bytes: 3408