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

const double EPS = 1e-8, PI = acos(-1);
inline bool eq(double a,double b){ return abs(b - a) < EPS; }
#define curr(P,i) P[i]
#define next(P,i) P[(i+1)%P.size()]
#define prev(P,i) P[(i+P.size()-1) % P.size()]
enum { OUT, ON, IN };

struct Geometory { // Geometory Library
  struct Point {
    double x, y;
    Point(){};
    Point(double x,double y):x(x),y(y){};
    Point operator+(const Point& b) const { return Point(x + b.x,y + b.y); }
    Point operator-(const Point& b) const { return Point(x - b.x,y - b.y); }
    Point operator*(const double b) const { return Point(x * b,y * b); }
    Point operator*(const Point& b) const { return Point(x * b.x - y * b.y,x * b.y + y * b.x); }
    Point operator/(const double b) const { return Point(x / b,y / b); }
    bool operator< (const Point& b) const { return x != b.x ? x < b.x : y < b.y; }
    bool operator==(const Point& b) const { return eq(x,b.x) && eq(y,b.y); }
    double norm(){ return x * x + y * y; }
    double arg(){ return atan2(x,y); }
    double abs(){ return sqrt(norm()); }
    Point rotate(double theta){ return Point(cos(theta) * x - sin(theta) * y,sin(theta) * x + cos(theta) * y); }
    Point rotate90(){ return Point(-y,x); }
  };

  struct Line {
    Point a, b;
    Line(){};
    Line(Point a,Point b):a(a),b(b){};
  };
  struct Segment {
    Point a, b;
    Segment(){};
    Segment(Point a,Point b):a(a),b(b){};
  };
  struct Circle {
    Point p; double r;
    Circle(){};
    Circle(Point p, double r) : p(p),r(r){};
  };
  typedef vector< Point > Polygon;
  typedef vector< Segment > Segments;
  typedef vector< Line > Lines;
  typedef vector< Circle > Circles;
  typedef pair< Point, Point > PointPoint;

  double cross(const Point& a,const Point& b){
    return a.x * b.y - a.y * b.x;
  }
  double dot(const Point& a,const Point& b){
    return a.x * b.x + a.y * b.y;
  }
  int ccw(const Point& a,Point b,Point c){
    b = b - a, c = c - a;
    if(cross(b,c) > 0)    return +1;  // a → b で 反時計方向におれて c
    if(cross(b,c) < 0)    return -1; // a → b で 時計方向におれて c
    if(dot(b,c) < 0)      return +2;  // c -- a -- bで一直線上
    if(b.norm() < c.norm()) return -2; // a -- b -- cで一直線上
    return 0;  // a -- c -- bで一直線上
  }
  bool Intersect(const Segment& s, const Segment& t){
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
  }
  PointPoint Crosspoint(const Circle& c1,const Circle& c2){ //OK
    double d = (c1.p - c2.p).abs();
    double s = (c1.r + c2.r + d) / 2;
    double S = sqrt( s * ( s - c1.r) * ( s - c2.r) * ( s - d));
    double h = 2 * S / d;
    Point v = ( c2.p - c1.p) / ( c2.p - c1.p).abs();
    double m = sqrt( c1.r * c1.r - h * h);
    return PointPoint( c1.p + v * m + Point(0,1) * h * v, c1.p + v * m - Point(0,1) * h * v);
  }
};

Geometory geo;
typedef Geometory::Point P;
typedef Geometory::Line L;
typedef Geometory::Segment S;
typedef Geometory::Circle C;
struct node{
  double cost;
  P pos;
  int nowy, nowx;
  bool operator < (const node &left) const {
    return cost > left.cost;
  }
};
typedef pair< int, int > POS;
typedef pair< double, P > PS;

int main(){
  int n;
  C prev, now;
  S seg[101];
  bool used[101][101];

  while(scanf("%d", &n), n){
    scanf("%lf %lf %lf", &prev.p.x, &prev.p.y, &prev.r);
    seg[0] = S( prev.p, prev.p);
    for(int i = 1; i < n; i++){
      scanf("%lf %lf %lf", &now.p.x, &now.p.y, &now.r);
      Geometory::PointPoint pp = geo.Crosspoint( prev, now);
      seg[i] = S(pp.first,pp.second);
      prev = now;
    }
    seg[n] = S( prev.p, prev.p);

    priority_queue< node > que;
    que.push((node){ 0, seg[0].a, 0, 0});
    memset( used, false, sizeof used);
    double ret;
    while(!que.empty()){
      node p = que.top(); que.pop();
      if(p.nowy == n){ ret = p.cost; break; }
      if(used[p.nowy][p.nowx]++) continue;
      for(int i = p.nowy + 1; i <= n; i++){
        S s1 = S( p.pos, seg[i].a), s2 = S( p.pos, seg[i].b);
        bool flag1 = true, flag2 = true;
        for(int j = i - 1; j > p.nowy; j--){
          if(!geo.Intersect( s1, seg[j])){
            flag1 = false;
            break;
          }
        }
        for(int j = i - 1; j > p.nowy; j--){
          if(!geo.Intersect( s2, seg[j])){
            flag2 = false;
            break;
          }
        }
        if(flag1) que.push((node){ p.cost + (s1.a - s1.b).abs(), s1.b, i, 0});
        if(flag2) que.push((node){ p.cost + (s2.a - s2.b).abs(), s2.b, i, 1});
      }
    }
    printf("%.7lf\n", ret);
  }
}

Measured memory_bytes: 1296