#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef complex<double> P;
typedef pair<P,P> Edge;
typedef long long ll;

const double PI=4*atan(1.0);
const int MAX_SIZE = 10000;

const double INF=1e+10;
int N;
double xs[101];
double ys[101];
double rs[101];
P cps[101];
P ps[1001];
double d[301][301];
int prv[301][301];
// 座標の回転(座標pにある点を,半時計回りにa(ラジアン)回転)
P roundPoint(P p,double a){
	return P(cos(a)*p.real()-sin(a)*p.imag(),sin(a)*p.real()+cos(a)*p.imag());
}
// 2円の交点を求める
pair<P,P> crossPointsTwoCircle(P c1,double r1,P c2,double r2){
  double a=abs(c1-c2);
  //double b=sqrt(r1*r1-(a/2)*(a/2));
  double tmp=((r1*r1-r2*r2+a*a)/(2*a));
  double b=sqrt(r1*r1-tmp*tmp);
  P p=c1-c2;p/=abs(p);
  p=roundPoint(p,PI/2);
  P p1=p;
  P p2=p;p2*=-1;
  p1*=b;p2*=b;
  P cp=(c2*tmp+c1*(a-tmp));
  cp*=(1.0/a);
  P res1=cp+p1;
  P res2=cp+p2;
  return make_pair(res1,res2);
}
// 内積
double dot(P a, P b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}
// 外積
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
// 点a,bを端点とする線分と点cとの距離
double distance_ls_p(P a, P b, P c) {
  if ( dot(b-a, c-a) < EPS ) return abs(c-a);
  if ( dot(a-b, c-b) < EPS ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}
// 円の中にaがあるか
bool isDotInCiecle(P cp,double r,P a){
  double dist=abs(cp-a);
  if(EQ(dist,r)||dist<r)return true;
  return false;
}
bool isCircleCrossLine(P a,P b,P c,double r){
  double d1 = abs(a-c);
  double d2 = abs(b-c);
  // 線分が中に含まれるとき、ここのコメントアウトをはずせばtrue(交差)となる
  if(d1<r&&d2<r)return true;
  double d = distance_ls_p(a,b,c);
  return (EQ(d,r)||d<r);
}
// 点a,bを通る直線と点cの間の距離
double distance_l_p(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}
// 円と直線の交点計算
// 接する場合は同じ点を２つ返す
vector<P> calcCrossPointLineAndCircle(P a,P b,P c,double r){
  vector<P> res;
  // もし直線と円がcrossしないなら、空リスト
  if(!isCircleCrossLine(a,b,c,r))return res;
  for(int i=0;i<2;i++){
    double x=distance_l_p(a,b,c);
    double y=sqrt(r*r-x*x);
    P e=(b-a);e/=abs(e);e=roundPoint(e,(2*i+1)*PI/2);
    P e2=e;e2*=x;
    P cp2=c+e2;
    P addV=(b-a);addV/=abs(addV);addV*=y;
    P res1=cp2+addV;
    addV*=-1;
    P res2=cp2+addV;
    // 今回求めた点が線分に乗ってない場合、向きを変えて再計算
    if(!EQ(0,distance_l_p(a,b,res1)))continue;
    res.push_back(res1);
    res.push_back(res2);
    return res;
  }
}
// 円と線分の交点計算
vector<P> calcCrossPointSegmentAndCircle(P a,P b,P c,double r){
  // 直線との交点計算
  vector<P> v=calcCrossPointLineAndCircle(a,b,c,r);
  vector<P> res;
  for(int i=0;i<(int)v.size();i++){
    // 線分と今回の点の距離が0ならリストへ
    double dis=distance_ls_p(a,b,v[i]);
    if(EQ(dis,0))res.push_back(v[i]);
  }
  return res;
}

// 線分a,bが円の内側にあるか
// fromからtoの円について調査する
bool check(P a,P b,int from,int to){
  vector<P> points;
  // 線分a-bと各円との交点を全列挙する
  for(int i=from;i<=to;i++){
    // 線分との交点を取得
    vector<P> res=calcCrossPointSegmentAndCircle(a,b,cps[i],rs[i]);
    for(int j=0;j<(int)res.size();j++)
      points.push_back(res[j]);
    // もし線分がない円が存在すれば、false
    if(res.size()==0||
       (!(i==from||i==to)&&(res.size()==1)))
      return false;
  }
  // pointsの点がそれぞれ2つ以上の点の内部にあるか
  for(int i=0;i<(int)points.size();i++){
    int cnt=0;
    for(int j=0;j<N;j++)
      if(isDotInCiecle(cps[j],rs[j],points[i]))cnt++;
    if(cnt<2)return false;
  }
  return true;
}

int main(){

  while(cin>>N&&N){
    for(int i=0;i<N;i++){
      cin>>xs[i]>>ys[i]>>rs[i];
      cps[i]=P(xs[i],ys[i]);
    }
    for(int i=1;i<N;i++){
      pair<P,P> p2=crossPointsTwoCircle(cps[i-1],rs[i-1],cps[i],rs[i]);
      ps[2*(i-1)]=p2.first;
      ps[2*(i-1)+1]=p2.second;
    }
    for(int i=0;i<=2*N-1;i++)
      for(int j=0;j<=2*N-1;j++)
    	if(i==j)d[i][j]=0;
    	else d[i][j]=INF;
    const int s=(N-1)*2;
    const int g=(N-1)*2+1;
    ps[(N-1)*2]=cps[0];
    ps[(N-1)*2+1]=cps[N-1];
    // for(int i=0;i<=2*N-1;i++)
    //   cout<<ps[i]<<" ";
    // cout<<endl;
    for(int i=0;i<=2*(N-1)+1;i++){
      for(int j=i+1;j<=2*(N-1)+1;j++){
	// if(i==10&&j==14){
	//   cout<<endl;
	// }
	int from=i/2;
	int to=j/2;
	if(i==2*N-2)from=0;
	else if(i==2*N-1)from=N-1;
	if(j==2*N-2)to=0;
	else if(j==2*N-1)to=N-1;
	int a=min(from,to);
	int b=min(N-1,max(from,to)+1);
    	// 条件を満たす線分を使う
    	if(check(ps[i],ps[j],a,b)){
	  //cout<<i<<" "<<j<<endl;
	  d[i][j]=d[j][i]=abs(ps[i]-ps[j]);
	  prv[i][j]=i;
	  prv[j][i]=j;
	}
      }
    }
    // for(int i=0;i<=2*N-1;i++)
    //   prv[i][i]=i;
    // floyd
    for(int i=0;i<=2*N-1;i++){
      for(int j=0;j<=2*N-1;j++){
    	for(int k=0;k<=2*N-1;k++){
    	  //d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
	  if(d[j][k]>d[j][i]+d[i][k]){
	    d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
	    // int cp=k;
	    // while(cp!=i){
	    //   prv[j][cp]=prv[i][cp];
	    //   cp=prv[i][cp];
	    // }
	  }
	}
      }
    }
    // int cp=g;
    // while(1){
    //   cout<<cp<<" ";
    //   if(cp==s)break;
    //   cp=prv[s][cp];
    // }
    // cout<<endl;
    printf("%.10f\n",d[s][g]);
    //break;
  }
  
  return 0;
}

Measured memory_bytes: 1740