#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

#define INF (DBL_MAX/4)
#define EPS (1e-10)
#define eq(a, b) (fabs((a)-(b)) < EPS)
#define lt(a, b) ((a)-(b) < -EPS)
#define le(a, b) (eq(a, b) || lt(a, b))

struct Point {
  double x, y;
  Point(){}
  Point(double x, double y):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(x*a, y*a); }
  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;
  }
};
using Vector = Point;

double dot(Vector a, Vector b) { return a.x*b.x+a.y*b.y; }
double cross(Vector a, Vector b) { return a.x*b.y-a.y*b.x; }
double norm(Vector v) { return dot(v, v); }
double abs(Vector v) { return sqrt(norm(v)); }

#define CCW +1
#define CW -1
#define BACK -2
#define FRONT +2
#define ON 0
int ccw(Point p0, Point p1, Point p2) {
  Vector a = p1-p0;
  Vector b = p2-p0;
  if(cross(a, b) > EPS) return CCW;
  if(cross(a, b) < -EPS) return CW;
  if(dot(a, b) < -EPS) return BACK;
  if(norm(a) < norm(b)) return FRONT;
  return ON;
}

bool intersect(Point p1, Point p2, Point p3, Point p4) {
  return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 &&
	  ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0);
}

double getDistance(Point a, Point b) {
  return abs(a-b);
}

struct Segment {
  Point s, t;
  Segment(){}
  Segment(Point s, Point t):s(s), t(t){}
};
using Line = Segment;

bool intersect(Segment s1, Segment s2) {
  return intersect(s1.s, s1.t, s2.s, s2.t);
}

struct Circle {
  Point p;
  double r;
  Circle(){}
  Circle(Point p, double r):p(p), r(r){}
};

bool intersect(Circle c1, Circle c2) {
  double d = getDistance(c1.p, c2.p);
  return le(d, c1.r+c2.r) && !lt(d, fabs(c1.r-c2.r));
}

double arg(Vector p) { return atan2(p.y, p.x); }
Vector polar(double a, double r) { return Point(cos(r)*a, sin(r)*a); }
vector<Point> getCrossPoints(Circle c1, Circle c2) {
  vector<Point> res;
  if(!intersect(c1, c2)) return res;
  double d = abs(c1.p-c2.p);
  double a = acos((c1.r*c1.r+d*d - c2.r*c2.r)/(2*c1.r*d));
  double t = arg(c2.p-c1.p);
  res.push_back(c1.p+polar(c1.r, t+a));
  res.push_back(c1.p+polar(c1.r, t-a));
  return res;
}

struct edge {
  int to;
  double cost;
  edge(){}
  edge(int to, double cost):to(to), cost(cost){}
};

int n;
vector<Circle> cs;
vector< vector<Point> > xp;
vector<Segment> segs;
vector< vector<edge> > graph;
int S, T;

double dijkstra() {
  vector<double> mincost(graph.size(), INF);
  priority_queue<Pi, vector<Pi>, greater<Pi> > que;
  mincost[S] = 0;
  que.emplace(0, S);
  while(!que.empty()) {
    Pi p = que.top(); que.pop();
    int v = p.second;
    if(v == T) return mincost[v];
    if(mincost[v] < p.first) continue;
    for(edge &e : graph[v]) {
      if(e.cost + mincost[v] < mincost[e.to]) {
	mincost[e.to] = e.cost + mincost[v];
	que.emplace(mincost[e.to], e.to);
      }
    }
  }
  return -1;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(cin >> n, n) {
    resz(cs, n);
    rep(i, n) cin >> cs[i].p.x >> cs[i].p.y >> cs[i].r;

    resz(xp, n-1);
    resz(segs, n-1);
    rep(i, n-1) {
      xp[i] = getCrossPoints(cs[i], cs[i+1]);
      assert((int)xp[i].size() == 2);
      segs[i] = Segment(xp[i][0], xp[i][1]);
    }

    resz(graph, 2*n);
    S = 2*n-2, T = 2*n-1;
    //rep(i, 2) graph[S].emplace_back(i, getDistance(cs[0].p, xp[0][i]));
    //rep(i, 2) graph[2*(n-2)+i].emplace_back(T, getDistance(xp[n-2][i], cs[n-1].p));
    rep(i, n-1) rep(j, 2) {
      double dist = getDistance(cs[0].p, xp[i][j]);
      Segment s = Segment(cs[0].p, xp[i][j]);
      rep(k, i+1) {
	if(!intersect(s, segs[k])) dist = INF;
      }
      if(dist != INF) graph[S].emplace_back(2*i+j, dist);
    }
    rep(i, n-1) rep(j, 2) {
      double dist = getDistance(xp[i][j], cs[n-1].p);
      Segment s = Segment(xp[i][j], cs[n-1].p);
      reps(k, i, n-1) {
	if(!intersect(s, segs[k])) dist = INF;
      }
      if(dist != INF) graph[2*i+j].emplace_back(T, dist);
    }
    {
      double dist = getDistance(cs[0].p, cs[n-1].p);
      Segment s = Segment(cs[0].p, cs[n-1].p);
      rep(i, n-1) {
	if(!intersect(s, segs[i])) dist = INF;
      }
      if(dist != INF) graph[S].emplace_back(T, dist);
    }

    rep(i, n-1) reps(j, i, n-1) {
      rep(k, 2) rep(l, 2) {
	if(i == j && k == l) continue;
	double dist = getDistance(xp[i][k], xp[j][l]);
	Segment s = Segment(xp[i][k], xp[j][l]);
	reps(m, i, j+1) {
	  if(!intersect(s, segs[m])) dist = INF;
	}
	if(dist != INF) graph[2*i+k].emplace_back(2*j+l, dist);
      }
    }

    cout << dijkstra() << endl;
  }

  return 0;
}

Measured memory_bytes: 3900