#include <iostream>
#include <algorithm>
#include <limits>
#include <complex>
#include <vector>
#include <queue>
#include <cmath>

//#define _DEBUG
//#ifdef _DEBUG
//#endif

using namespace std;

typedef complex< double > Point;
typedef complex< double > Vector;
const double kEps = 1e-8;
const double kInf = numeric_limits< double >::max() / 2;

struct Circle {
  Point cntr;
  double r;

  friend istream & operator >> (istream &is, Circle &rc) {
    double x, y;
    is >> x >> y >> rc.r, rc.cntr = Point(x, y);
    return is;
  }
};

struct PQNode {
  int u;
  double cst;

  PQNode(int _u, double _cst) { u = _u, cst = _cst; }
  bool operator > (const PQNode &rpq) const { return cst > rpq.cst + kEps; }
};

typedef priority_queue< PQNode, vector< PQNode >, greater< PQNode > > PQue;

struct Edge {
  int v, nxt;
  double ln;
} edges[100000];

int N, S, T;
Circle crc[105];
Point p[210];
int gph[210], edge_cnt;
double f[210];

void read_circle(void);
void build_graph(void);
void solve(void);
bool is_intr(Point, Point, Point, Point);
void add_edge(int, int, double);

inline bool fle(double a, double b) { return a < b + kEps; }
inline bool flt(double a, double b) { return a + kEps < b; }
inline double cross(Vector u, Vector v) { return imag(conj(u) * v); }

int main() {
  cout.setf(ios::fixed), cout.precision(4);
  while (cin >> N, N) {
    read_circle();
    build_graph();
    solve();
  }

  return 0;
}

void read_circle(void) {
  for (int i = 0; i < N; ++i)
    cin >> crc[i];
}

void build_graph(void) {
  for (int i = 0; i < N - 1; ++i) {
    Point &c1 = crc[i].cntr, &c2 = crc[i + 1].cntr;
    double r1 = crc[i].r, r2 = crc[i + 1].r, d, cos_tht;

    d = abs(c2 - c1);
    cos_tht = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d);

    Vector rv1, rv2, u1, u2;

    rv1 = Vector(cos_tht, sqrt(1 - cos_tht * cos_tht));
    rv2 = Vector(cos_tht, -sqrt(1 - cos_tht * cos_tht));
    u1 = u2 = c2 - c1;
    u1 = u1 * rv1 * r1 / d, u2 = u2 * rv2 * r1 / d;

    p[2 * i] = c1 + u1, p[2 * i + 1] = c1 + u2;

#ifdef _DEBUG
  cout << 2 * i << ": " << p[2 * i] << endl;
  cout << 2 * i + 1 << ": " << p[2 * i + 1] << endl;
#endif
  }
  p[S = 2 * (N - 1)] = crc[0].cntr, p[T = 2 * (N - 1) + 1] = crc[N - 1].cntr;

  bool is_valid;

  fill(&gph[0], &gph[2 * N], -1), edge_cnt = 0;
  for (int i = 0; i < 2 * (N - 1); ++i) {
    is_valid = true;
    for (int j = 0; j < i / 2 && is_valid; ++j)
      if (!is_intr(p[S], p[i], p[2 * j], p[2 * j + 1]))
        is_valid = false;
    if (is_valid)
      add_edge(S, i, abs(p[i] - p[S]));
  }

  for (int i = 0; i < 2 * (N - 1); ++i) {
    is_valid = true;
    for (int j = i / 2 + 1; j < N - 1 && is_valid; ++j)
      if (!is_intr(p[i], p[T], p[2 * j], p[2 * j + 1]))
        is_valid = false;
    if (is_valid)
      add_edge(i, T, abs(p[T] - p[i]));
  }

  for (int i = 0; i < 2 * (N - 1); ++i)
    for (int j = i + 1; j < 2 * (N - 1); ++j) {
      is_valid = true;
      for (int k = i / 2 + 1; k < j / 2 && is_valid; ++k)
        if (!is_intr(p[i], p[j], p[2 * k], p[2 * k + 1]))
          is_valid = false;
      if (is_valid)
        add_edge(i, j, abs(p[j] - p[i]));
    }

  is_valid = true;
  for (int i = 0; i < N - 1 && is_valid; ++i)
    if (!is_intr(p[S], p[T], p[2 * i], p[2 * i + 1]))
      is_valid = false;
  if (is_valid)
    add_edge(S, T, abs(p[T] - p[S]));

#ifdef _DEBUG
  for (int u = 0; u < 2 * N; ++u) {
    cout << "u = " << u << endl;
    for (int eid = gph[u]; eid != -1; eid = edges[eid].nxt) {
      int v = edges[eid].v;
      double ln = edges[eid].ln;
      cout << "  v = " << v << ", ln = " << ln << endl;
    }
  }
#endif
}

void solve(void) {
  PQue pq;
  double res = 0;

  fill(&f[0], &f[2 * N], kInf), f[S] = 0, pq.push(PQNode(S, 0));
  while (!pq.empty()) {
    PQNode tp(pq.top());  pq.pop();
    int u = tp.u;
    double cst = tp.cst;

    if (flt(f[u], cst)) continue;
    if (u == T) { res = cst;  break; }

    for (int eid = gph[u]; eid != -1; eid = edges[eid].nxt) {
      int v = edges[eid].v;
      double ln = edges[eid].ln;

      if (flt(f[u] + ln, f[v]))
        f[v] = f[u] + ln, pq.push(PQNode(v, f[v]));
    }
  }

  cout << res << endl;
}

bool is_intr(Point p1, Point p2, Point p3, Point p4) {
  return (fle(min(real(p3), real(p4)), max(real(p1), real(p2))) &&
          fle(min(real(p1), real(p2)), max(real(p3), real(p4))) &&
          fle(min(imag(p3), imag(p4)), max(imag(p1), imag(p2))) &&
          fle(min(imag(p1), imag(p2)), max(imag(p3), imag(p4))) &&
          fle(cross(p3 - p1, p3 - p4) * cross(p3 - p2, p3 - p4), 0) &&
          fle(cross(p1 - p3, p1 - p2) * cross(p1 - p4, p1 - p2), 0)
          );
}

void add_edge(int u, int v, double ln) {
  Edge &r1 = edges[edge_cnt], &r2 = edges[edge_cnt + 1];
  r1.v = v, r1.ln = ln, r1.nxt = gph[u], gph[u] = edge_cnt;
  r2.v = u, r2.ln = ln, r2.nxt = gph[v], gph[v] = edge_cnt + 1;
  edge_cnt += 2;
}

Measured memory_bytes: 1428