//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double mEPS = 1e-10;
const double PI  = acos(-1.0);
const double INF = 1e9;

class Point{
public:
	double x, y;

	Point(double x = 0.0, double y = 0.0) : 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(a*x, a*y); }
	Point operator / (double a){ return Point(x / a, y / a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator < (const Point &p) const{
		return x != p.x ? x < p.x : y < p.y;
	}

	//EPS??????????°??????????
	bool operator == (const Point &p) const {
		return fabs(x - p.x) < mEPS && fabs(y - p.y) < mEPS;
	}

};
class Segment{
public:
	Point p1, p2;
};

class Circle{
public:
	Point c;
	double r;
};

typedef vector<Point> Polygon;
typedef Point Vector;
typedef Segment Line;

double arg(Vector p){ return atan2(p.y, p.x); }
Vector polar(double a, double r){ return Point(cos(r)*a, sin(r)*a); }
pair<Point, Point> getCrossPoints(Circle c1, Circle c2){
	double d = (c1.c - c2.c).abs();
	double a = acos((c1.r*c1.r + d*d - c2.r*c2.r) / (2 * c1.r*d));
	double t = arg(c2.c - c1.c);
	return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
}
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 getDistancePP(Point a, Point b){
	return (a - b).abs();
}
double getDistanceLP(Line l, Point p){
	return abs(cross(l.p2 - l.p1, p - l.p1) / (l.p2 - l.p1).abs());
}
int ccw(Point p0, Point p1, Point p2){

	//p0->p1???p0?§???????p1?????????????????????????????¨????????¨???

	//p0->p2??????????¨??????????????????¨???
	static const int COUNTER_CLOCKWISE = 1;
	//p0->p2???????¨??????????????????¨???
	static const int CLOCKWISE = -1;
	//p2,p0,p1????????§????????´?????????????????¨???
	static const int ONLINE_BACK = 2;
	//p0,p1,p2 ????????§????????´?????????????????´???
	static const int ONLINE_FRONT = -2;
	//p2 ????????? p0p1 ??????????????´???
	static const int ON_SEGMENT = 0;

	Vector a = p1 - p0;
	Vector b = p2 - p0;

	if (cross(a, b) > mEPS) return COUNTER_CLOCKWISE;
	if (cross(a, b) < -mEPS) return CLOCKWISE;
	if (dot(a, b) < -mEPS) return ONLINE_BACK;
	if (a.norm() < b.norm()) return ONLINE_FRONT;

	return ON_SEGMENT;

}
bool intersect(Segment s1, Segment s2){
	return(ccw(s1.p1, s1.p2, s2.p1) * ccw(s1.p1, s1.p2, s2.p2) <= 0 &&
		ccw(s2.p1, s2.p2, s1.p1) * ccw(s2.p1, s2.p2, s1.p2) <= 0);
}

// ??????l??????????????????????????±????????´??\????????????
bool isdirect(vector<Point>& ps, int s, int e, Segment& l){
  for(int i=s;i<e;++i){
	Segment s; s.p1 = ps[i*3+1], s.p2 = ps[i*3+2];
	if(!intersect(s,l)) return false;
  }
  return true;
}

struct Edge{
  int to;
  double cost;

  Edge(int t, double c): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
};
typedef vector< vector<Edge> > Graph;
void Dijkstra(const Graph& edges, vector<double>& d, int s){
  typedef pair<double,int> PDI;
  const int V = edges.size();
  priority_queue<PDI, vector<PDI>, greater<PDI> > pq;
  fill(d.begin(), d.end(), INF);
  d[s] = 0;
  pq.push(MP(0,s));

  while(!pq.empty()){
	PII pii = pq.top(); pq.pop();
	int v = pii.second;
	if(d[v] < pii.first) continue;
	for(int i=0;i<edges[v].size();++i){
	  const Edge& e = edges[v][i];
	  if(d[e.to] > d[v] + e.cost){
		d[e.to] = d[v] + e.cost;
		pq.push(MP(d[e.to], e.to));
	  }
	}
  }
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  while(cin>>N,N){
	vector<Circle> cs(N);
	REP(i,N)
	  cin >> cs[i].c.x >> cs[i].c.y >> cs[i].r;

	vector<Point> ps(N*3);
	REP(i,N-1){
	  ps[i*3] = cs[i].c;
	  auto pss = getCrossPoints(cs[i], cs[i+1]);
	  ps[i*3+1] = pss.first, ps[i*3+2] = pss.second;
	}
	ps[3*N-1] = ps[3*N-2] = ps[3*N-3] = cs[N-1].c;

	Graph G(3*N);
	REP(i,3*N) FOR(j,i+1,3*N){
	  Segment seg;
	  seg.p1 = ps[i], seg.p2 = ps[j];
	  if(isdirect(ps, i/3, j/3, seg)){
		G[i].PB(Edge(j, getDistancePP(ps[i], ps[j])));
		G[j].PB(Edge(i, getDistancePP(ps[i], ps[j])));				
	  }
	}
	vector<double> dist(3*N);
	Dijkstra(G, dist, 0);

	cout << fixed << setprecision(9) << dist[3*N-3] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 2048