#include<algorithm>
#include<complex>
#include<cstdio>
#include<iostream>
#include<queue>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)
template<class T> T at(vector<T> v, int i) {return v[i % v.size()];}

#define X real()
#define Y imag()

typedef double D;
typedef complex<D> P;
struct L{P a, b;};

const D EPS = 1e-8;

int sig(D a, D b = 0) {return a < b - EPS ? -1 : a > b + EPS ? 1 : 0;}

// 比較関数
namespace std {
  bool operator<(P a, P b) {return sig(a.X, b.X) ? a.X < b.X : a.Y < b.Y;}
  bool operator==(P a, P b) {return norm(a - b) < EPS;}
  bool operator<(L a, L b) {return a.a != b.a ? a.a < b.a : a.b < b.b;}
}

D sr(D a) {return sqrt(max(a, (D)0));}

// 内積
D dot(P a, P b) {return a.X * b.X + a.Y * b.Y;}
// 外積
D det(P a, P b) {return a.X * b.Y - a.Y * b.X;}

// 線分のベクトル
P vec(L a) {return a.b - a.a;}

// 線分abに対する点cの位置
enum CCW{FRONT = 1, RIGHT = 2, BACK = 4, LEFT = 8, ON = 16};
int ccw(P a, P b, P c) {
  int s = sig(det(b - a, c - a));
  if (s) return s > 0 ? LEFT : RIGHT;
  if (a == c || b == c) return ON;
  return (a < b) == (b < c) ? FRONT : (c < a) == (a < b) ? BACK : ON;
}

// 射影
P proj(P a, P b) {return a * dot(a, b) / norm(a);}
P perp(L l, P p) {return l.a + proj(vec(l), p - l.a);}

// 距離
D dLP(L l, P p) {return abs(det(vec(l), p - l.a)) / abs(vec(l));}
D dSP(L s, P p) {
  if (dot(vec(s), p - s.a) < 0) return abs(p - s.a);
  if (dot(vec(s), p - s.b) > 0) return abs(p - s.b);
  return dLP(s, p);
}

// 円
struct C{P c; D r;};

// 交差判定
bool iCP(C c, P p) {return sig(abs(p - c.c), c.r) <= 0;}
bool iCS(C c, L s) {return sig(c.r, dSP(s, c.c)) >= 0;}
bool iCSc(C c, L s) {return iCS(c, s) && sig(c.r, max(abs(s.a - c.c), abs(s.b - c.c))) <= 0;}

// 交点
pair<P, P> pCC(C a, C b) {
  D x = (norm(a.c - b.c) + a.r * a.r - b.r * b.r) / (2 * abs(a.c - b.c));
  P e = (b.c - a.c) / abs(b.c - a.c);
  P y = e * P(0, sr(a.r * a.r - x * x));
  return make_pair(a.c + e * x - y, a.c + e * x + y);
}
pair<P, P> pCL(C c, L l) {
  P x = perp(l, c.c);
  P y = vec(l) / abs(vec(l)) * sr(c.r * c.r - norm(x - c.c));
  return make_pair(x - y, x + y);
}

// 線分アレンジメント 隣の点への辺のみを持つ
vector<vector<int> > sArr(vector<L> s, vector<P> &vp) {
  //s = merge(s);
  rep (i, s.size()) {
    vp.push_back(s[i].a);
    vp.push_back(s[i].b);
  }
  //rep (i, s.size()) rep (j, i) if (iSS(s[i], s[j])) vp.push_back(pLL(s[i], s[j]));
  sort(vp.begin(), vp.end());
  vp.erase(unique(vp.begin(), vp.end()), vp.end());
  vector<vector<int> > g(vp.size());
  rep (i, s.size()) {
    vector<pair<D, int> > v;
    rep (j, vp.size()) if (ccw(s[i].a, s[i].b, vp[j]) == ON) {
      v.push_back(make_pair(norm(vp[j] - s[i].a), j));
    }
    sort(v.begin(), v.end());
    rep (j, v.size() - 1) {
      g[v[j + 1].second].push_back(v[j].second);
      g[v[j].second].push_back(v[j + 1].second);
    }
  }
  return g;
}

int main() {
  int n;
  while (cin >> n, n) {
    C c[n];
    rep (i, n) cin >> c[i].c.X >> c[i].c.Y >> c[i].r;
    vector<P> vp;
    vp.push_back(c[0].c);
    vp.push_back(c[n - 1].c);
    rep (i, n - 1) {
      pair<P, P> pp = pCC(c[i], c[i + 1]);
      vp.push_back(pp.first);
      vp.push_back(pp.second);
    }
    vector<L> vs;
    rep (i, vp.size()) rep (j, i) {
      L s = {vp[i], vp[j]};
      vector<P> v;
      rep (k, n) if (iCSc(c[k], s)) {
	pair<P, P> pp = pCL(c[k], s);
	if (ccw(s.a, s.b, pp.first) == ON) v.push_back(pp.first);
	if (ccw(s.a, s.b, pp.second) == ON) v.push_back(pp.second);
      }
      sort(v.begin(), v.end());
      rep (t, v.size() - 1) {
	bool ok = false;
	P m = (v[t] + v[t + 1]) / (D)2;
	rep (k, n) if (iCP(c[k], m)) {
	  ok = true;
	  break;
	}
	if (!ok) goto next;
      }
      vs.push_back(s);
    next:;
    }
    vector<P> p;
    vector<vector<int> > g = sArr(vs, p);
    int start = -1, goal = -1;
    rep (i, p.size()) if (p[i] == c[0].c) start = i;
    rep (i, p.size()) if (p[i] == c[n - 1].c) goal = i;
    D dis[p.size()];
    rep (i, p.size()) dis[i] = 1e100;
    priority_queue<pair<D, int>, vector<pair<D, int> >, greater<pair<D, int> > > que;
    que.push(make_pair(0, start));
    while (!que.empty()) {
      pair<D, int> now = que.top();
      que.pop();
      if (sig(dis[now.second], now.first) <= 0) continue;
      dis[now.second] = now.first;
      rep (i, g[now.second].size()) {
	que.push(make_pair(now.first + abs(p[now.second] - p[g[now.second][i]]), g[now.second][i]));
      }
    }
    printf("%.12lf\n", dis[goal]);
  }
  return 0;
}

Measured memory_bytes: 1692