#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef complex<double> Complex;
typedef pair<Complex, Complex> pcc;

pcc circles_intersect_points(Complex c1, double r1, Complex c2, double r2) {
  Complex u = c2 - c1;

  double d = abs(u);
  double d1 = (r1 * r1 - r2 * r2 + d * d) / (d * 2);
  double l = sqrt(r1 * r1 - d1 * d1);

  Complex v = Complex(u.imag(), -u.real()) / d;
  Complex g = c1 + u * (d1 / d);

  pcc ret;
  ret.fi = g + v * l;
  ret.se = g - v * l;
  return ret;
}

double det(Complex a, Complex b) {
  return a.real() * b.imag() - a.imag() * b.real();
}

bool line_segments_intersect(Complex a, Complex b, Complex c, Complex d) {
  double ta = det(a - c, d - c);
  double tb = det(b - c, d - c);
  double tc = det(c - a, b - a);
  double td = det(d - a, b - a);
  return ta * tb < 0 && tc * td < 0;
}

bool ok(const vector<pcc> &lines, Complex v1, Complex v2, ll p, ll q) {
  REP(i, p, q + 1) {
    if(!line_segments_intersect(lines[i].fi, lines[i].se, v1, v2)) {
      return false;
    }
  }
  return true;
}

int main(void) {
  ll N;
  while(cin >> N, N) {
    vector<Complex> P(N);
    vector<ll> R(N);
    REP(i, 0, N) {
      ll x, y;
      cin >> x >> y >> R[i];
      P[i] = Complex(x, y);
    }

    vector<pcc> lines(N - 1);
    REP(i, 0, N - 1) {
      lines[i] = circles_intersect_points(P[i], R[i], P[i + 1], R[i + 1]);
    }

    Complex S = P[0], G = P[N - 1];
    vector<Complex> points(N * 2);
    REP(i, 0, N - 1) {
      points[i * 2] = lines[i].fi;
      points[i * 2 + 1] = lines[i].se;
    }
    points[N * 2 - 2] = S;
    points[N * 2 - 1] = G;

#define add_edge(u, v) { \
  E[u].push_back(v); \
  E[v].push_back(u); \
}

    vector<vector<ll>> E(N * 2);
    if(ok(lines, S, G, 0, N - 2)) add_edge(N * 2 - 2, N * 2 - 1);
    REP(i, 0, N - 1) {
      if(ok(lines, S, lines[i].fi, 0, i - 1)) add_edge(N * 2 - 2, i * 2);
      if(ok(lines, S, lines[i].se, 0, i - 1)) add_edge(N * 2 - 2, i * 2 + 1);
      if(ok(lines, lines[i].fi, G, i + 1, N - 2)) add_edge(i * 2, N * 2 - 1);
      if(ok(lines, lines[i].se, G, i + 1, N - 2)) add_edge(i * 2 + 1, N * 2 - 1);
    }
    REP(i, 0, N - 1) REP(j, i + 1, N - 1) {
      if(ok(lines, lines[i].fi, lines[j].fi, i + 1, j - 1)) add_edge(i * 2, j * 2);
      if(ok(lines, lines[i].fi, lines[j].se, i + 1, j - 1)) add_edge(i * 2, j * 2 + 1);
      if(ok(lines, lines[i].se, lines[j].fi, i + 1, j - 1)) add_edge(i * 2 + 1, j * 2);
      if(ok(lines, lines[i].se, lines[j].se, i + 1, j - 1)) add_edge(i * 2 + 1, j * 2 + 1);
    }

    struct state {
      ll v;
      double cost;
      bool operator<(const state s) const { return cost > s.cost; }
    };

    vector<double> dp(N * 2, 1e20);
    priority_queue<state> q;
    q.push((state) { N * 2 - 2, 0 });

    while(q.size()) {
      ll v = q.top().v;
      double cost = q.top().cost;
      q.pop();
      if(dp[v] <= cost) continue;
      dp[v] = cost;
      for(ll nv : E[v]) {
        double ncost = cost + abs(points[v] - points[nv]);
        if(dp[nv] > ncost) q.push((state) { nv, ncost });
      }
    }

    printf("%.15lf\n", dp[N * 2 - 1]);
  }
}


Measured memory_bytes: 3328