#include <iostream>
#include <math.h>
#include <vector>
#include <utility>
#include <stdio.h>
#define inf 1e9
#define eps 1e-9

using namespace std;

struct vec2d{
  double x, y;
  vec2d(){}
  vec2d(double x, double y){
    this->x = x, this->y = y;
  }
  double add(double a, double b){
    if(fabs(a+b) < eps * (fabs(a) + fabs(b))) return 0.0;
    return a+b;
  }
  vec2d operator+(vec2d ope){
    return vec2d(add(x, ope.x), add(y, ope.y));
  }
  vec2d operator-(vec2d ope){
    return vec2d(add(x, -ope.x), add(y, -ope.y));
  }
  vec2d operator*(double t){
    return vec2d(x*t, y*t);
  }
  vec2d operator/(double t){
    return vec2d(x/t, y/t);
  }
  double dot(vec2d ope){
    return add(x*ope.x, y*ope.y);
  }
  double cross(vec2d ope){
    return add(x*ope.y, -y*ope.x);
  }
  double norm(){
    double d2 = dot(*this);
    if(d2 > 0) return sqrt(d2);
    return 0.0;
  }
};

double distPP(vec2d p, vec2d q){
  return (p-q).norm();
}
double distSP(vec2d p, vec2d q, vec2d x){
  if((x-p).dot(q-p) <= 0) return distPP(p, x);
  if((x-q).dot(p-q) <= 0) return distPP(q, x);
  return fabs((x-p).cross(q-p) / distPP(p, q));
}
bool isOnS(vec2d p, vec2d q, vec2d x)
{
  return (p-x).cross(q-x) == 0 && (p-x).dot(q-x) <= 0;
}
bool isCross(vec2d p, vec2d q, vec2d r, vec2d s)
{
  if((q-p).cross(s-r) == 0){
    return isOnS(p, q, r) || isOnS(p, q, s) || isOnS(r, s, p) || isOnS(r, s, q);
  }
  double t = (r-p).cross(s-r) / (q-p).cross(s-r);
  vec2d x = p + (q-p)*t;
  return isOnS(p, q, x) && isOnS(r, s, x);
}

void getCrossPointCC(vec2d c1, double r1, vec2d c2, double r2, vec2d &lp, vec2d &rp)
{
  vec2d v = c2 - c1, n;
  double d = v.norm();
  double x = (r1*r1-r2*r2+d*d) / (2*d);

  v = v*(x/d);
  n = vec2d(-v.y, v.x);
  if(x >= 0){
    n = n*(sqrt(r1*r1-x*x) / n.norm());
    lp = c1 + v - n, rp = c1 + v + n;
  }
  else{
    n = n*(sqrt(r2*r2-(d-x)*(d-x))) / n.norm();
    lp = c1 + v + n, rp = c1 + v - n;
  }
}

int n;
vec2d p[105];
double r[105];
vector<pair<vec2d, int> > vec;
vec2d lp[305], rp[305];
double G[305][305];
double dist[305][305];

int main(void)
{
  while(1){
    cin >> n;
    if(n == 0) break;
    for(int i = 1; i <= n; i++){
      cin >> p[i].x >> p[i].y >> r[i];
    }

    vec.clear();
    vec.push_back(make_pair(p[1], 0)), vec.push_back(make_pair(p[n], n));
    for(int i = 1; i < n; i++){
      vec2d u, v;
      getCrossPointCC(p[i], r[i], p[i+1], r[i+1], u, v);
      vec.push_back(make_pair(u, i)), vec.push_back(make_pair(v, i));
      lp[i] = u, rp[i] = v;
    }
    //cout << vec.size() << endl;

    /*for(int i = 0; i <vec.size(); i++){
      cout << vec[i].first.x << " " << vec[i].first.y << endl;
      }*/

    int V = vec.size();
    for(int i = 0; i < V; i++){
      for(int j = 0; j < V; j++){
	if(i == j) G[i][j] = 0;
	else G[i][j] = inf;
      }
    }
   

    for(int i = 0; i < V; i++){
      for(int j = 0; j < V; j++){
	if(i >= j) continue;
	bool flag = true;
	int L = min(vec[i].second, vec[j].second);
	int R = max(vec[i].second, vec[j].second);
	for(int k = L+1; k <= R-1; k++){
	  if(!isCross(vec[i].first, vec[j].first, lp[k], rp[k])) flag = false;
	}
	if(flag) G[i][j] = G[j][i] = distPP(vec[i].first, vec[j].first);
      }
    }

    /*for(int i = 0; i < V; i++){
      for(int j = 0; j < V; j++){
	cout << G[i][j] << " ";
      }
      cout << endl;
      }*/

    for(int i = 0; i < V; i++){
      for(int j = 0; j < V; j++){
	dist[i][j] = G[i][j];
      }
    }
    for(int k = 0; k < V; k++){
      for(int i = 0; i < V; i++){
	for(int j = 0; j < V; j++){
	  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
      }
    }
    printf("%11f\n", dist[0][1]);
  }

  return 0;
}



Measured memory_bytes: 4172