#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<complex>
#include<queue>
#include<cassert>
#include<algorithm>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define inf (1<<28) 
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)
 
using namespace std;
 
class Point
{
  public:
  double x,y;
 
  Point(double x = -inf,double y = -inf): x(x),y(y){}
 
  Point operator + (Point p ){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}//※イケメンに限る
 
  bool operator < (const Point& p) const{ return x != p.x?x<p.x:y<p.y; }
};
 
struct Segment
{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
};
 
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
 
double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }
 
double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }
 
double norm(Point a) {  return a.x*a.x+a.y*a.y; }
 
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }
 
double toRad(double agl){ return agl*M_PI/180.0; }
 
int ccw(Point p0,Point p1,Point p2)
{
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}
 
double abs(Point p)
{
  return sqrt(norm(p));
}
 
bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}
 
Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}
 
double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}
 
double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}
Point crosspoint(Line l, Line m) {
  double A = cross(l.p2 - l.p1, m.p2 - m.p1);
  double B = cross(l.p2 - l.p1, l.p2 - m.p1);
  if (abs(A) < EPS && abs(B) < EPS) return m.p1; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return m.p1 +   (m.p2 - m.p1) * (B / A);
}
 
struct P
{
  int to;
  double cost;
  P(int to=-inf,double cost=-inf):to(to),cost(cost){}
};
 
struct Pox
{
  int cur;
  double cost;
  Pox(int cur=-inf,double cost=-inf):cur(cur),cost(cost){}
  bool operator < (const Pox& a)const{ return cost > a.cost; }
 
};
 
struct Circle
{
  Point p;
  double r;
  Circle(Point p=Point(),double r=-inf):p(p),r(r){}
};
 
pair<Point, Point> circle_circle_intersect( Point C1, double r1, Point C2, double r2) {
  complex<double> c1(C1.x,C1.y);
  complex<double> c2(C2.x,C2.y);
  complex<double> A = conj(c2-c1), B = (r2*r2-r1*r1-(c2-c1)*conj(c2-c1)), C = r1*r1*(c2-c1);
  complex<double> D = B*B-4.0*A*C;
  complex<double> z1 = (-B+sqrt(D))/(2.0*A)+c1, z2 = (-B-sqrt(D))/(2.0*A)+c1;
  return pair<Point, Point>(Point(z1.real(),z1.imag()),Point(z2.real(),z2.imag()));
}
 
int n;
 
int main()
{
 
  while(cin >> n,n)
    {
      vector<Circle> cs(n);
      vector<Segment> ss(n-1);
      vector<Point> ps;
      rep(i,n)cin >> cs[i].p.x >> cs[i].p.y >> cs[i].r;
      
      ps.push_back(cs[0].p);
      rep(i,n-1)
    {
 
      pair<Point,Point> pp = circle_circle_intersect(cs[i].p,cs[i].r,cs[i+1].p,cs[i+1].r);
      ss[i].p1 = pp.first,ss[i].p2 = pp.second; 
      ps.push_back(pp.first);
      ps.push_back(pp.second);
      ps.push_back(cs[i+1].p);
    }
 
      int N = n + (n-1)*2;
      vector<vector<P> > G(N,vector<P>());
 
      int pssize = ps.size();
      rep(i,pssize)
	{
	  //cout << "from " << i << endl;
	  rep(j,pssize)
	    {
	      if(i == j)continue;	      
	      bool pass = true;
	      for(int k=1;k<=j;k+=3)
		{
		  if(k < i)continue;
		  //cout << "Segment( ( "<< ps[i].x << "," << ps[i].y << ") , (" << ps[j].x << "," << ps[j].y << ") ) and Segment( (" << ps[k].x << "," << ps[k].y << ") , (" << ps[k+1].x << "," << ps[k+1].y << ") )" << endl;            
		  //cout << "result : " << intersectSS(Segment(ps[i],ps[j]),Segment(ps[k],ps[k+1])) << endl;
		  if(!intersectSS(Segment(ps[i],ps[j]),Segment(ps[k],ps[k+1])))
		    {
		      pass = false;
		      break;
		    }
		}
	      //cout <<"pass?" << pass << endl;
	      if(!pass)continue;
	      //cout << "IN!" << endl;
	      G[i].push_back(P(j,abs(ps[j]-ps[i])));
	    }
	}
      /*
	rep(i,G.size())
	{
	cout << i << "-th" << endl;
	rep(j,G[i].size())
        {
	cout << "(" << G[i][j].to << "," << G[i][j].cost << ") ";
        }
	cout << endl;
	}
      */
      double mincost[N];
      rep(i,N)mincost[i] = inf;
      mincost[0] = 0;
      priority_queue<Pox> Q;
      Q.push(Pox(0,0));
      while(!Q.empty())
	{
	  Pox pox = Q.top(); Q.pop();
	  if(pox.cur == N-1)
	    {
	      cout << setiosflags(ios::fixed) << setprecision(10) << pox.cost << endl;
	      goto Fin;
	    }
	  
	  rep(i,G[pox.cur].size())
	    {
	      P p = G[pox.cur][i];
	      if(mincost[p.to] > mincost[pox.cur] + p.cost)
		{
		  mincost[p.to] = mincost[pox.cur] + p.cost;
		  Q.push(Pox(p.to,mincost[p.to]));
		}
	    }
	}
      cout << "EEE" << endl; 
    Fin:;
    }
  return 0;
}

Measured memory_bytes: 2504