#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

#include <complex>
typedef complex<double> P;
#define LT(x, y) ((x) - (y) <= -EPS)
//２円の交点計算
vector<P> crossCircles(P c1, double r1, P c2, double r2){
    double d=abs(c2-c1);
    if ( LT(r1+r2, d) || LT(d, fabs(r1-r2)) )
    return vector<P>();
    double l = 0.5* ( (r1*r1-r2*r2)/d+d);
    double h = sqrt(r1*r1-l*l);
    vector<P> ret(2);
    ret[0]=P(l,+h)*(c2-c1)/d+c1;
    ret[1]=P(l,-h)*(c2-c1)/d+c1;
    return ret;
}
// 点cが線分a,b上にあるかないか(2)
int is_point_on_line(P a, P b, P c) {
  // |a-c| + |c-b| <= |a-b| なら線分上
  return (abs(a-c) + abs(c-b) < abs(a-b) + EPS);
}
// 外積 (cross product) : a×b = |a||b|sinΘ
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_ls(P a1, P a2, P b1, P b2) {
  if (( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < -EPS ) &&
          ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < -EPS ))
        return true;
  return is_point_on_line(a1, a2, b1) || is_point_on_line(a1, a2, b2) ||
             is_point_on_line(b1, b2, a1) || is_point_on_line(b1, b2, a2);
}
struct point{
	P p;int circle;
	point(P p,int circle):p(p),circle(circle){}
};
struct node{
    int index;double cost;
    node(int index,double cost):index(index),cost(cost){}
    bool operator<(const node& other)const{
        return cost>other.cost;
    }
};
const double MAX=INT_MAX/10;
int main(){
	cout.precision(16);
	int n;
	while(cin>>n,n){
		vi x(n),y(n),r(n);
		vector<point> points;
		vector<vector<point> > circle_to_points(n);
		REP(i,n){
			cin>>x[i]>>y[i]>>r[i];
			if(i>0){
				vector<P> ps=crossCircles(P(x[i],y[i]),r[i],P(x[i-1],y[i-1]),r[i-1]);
				points.push_back(point(ps[0],i));
				points.push_back(point(ps[1],i));
				circle_to_points[i].push_back(point(ps[0],i));
				circle_to_points[i].push_back(point(ps[1],i));
			}
		}
		points.push_back(point(P(x[0],y[0]),0));
		points.push_back(point(P(x[n-1],y[n-1]),n));
		vector<vector<double> > dist(points.size(),vector<double>(points.size(),MAX));
		REP(i,points.size()){
			REP(j,points.size()){
				bool flag=true;
				FOR(k,points[i].circle+1,points[j].circle){
					if(!is_intersected_ls(points[i].p,points[j].p,circle_to_points[k][0].p,circle_to_points[k][1].p)){
						flag=false;
						break;
					}
				}
				if(flag){
					dist[i][j]=abs(points[i].p-points[j].p);
				}
			}
		}
	
		priority_queue<node> q;
		q.push(node(points.size()-2,0));
		vector<double> cost(points.size(),MAX);
		cost[points.size()-2]=0;
		while(!q.empty()){
			node cnode=q.top();q.pop();
			if(cost[cnode.index]<cnode.cost){
				continue;
			}
			REP(i,points.size()){
				if(i!=cnode.index&&dist[cnode.index][i]!=MAX){
					double newcost=cnode.cost+dist[cnode.index][i];
					if(cost[i]>newcost){
						cost[i]=newcost;
						q.push(node(i,newcost));
					}
				}
			}
		}
		cout<<cost[points.size()-1]<<endl;
	}
}

Measured memory_bytes: 1532