#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
#include <array>
using namespace std;
#define rep(i,n) for (int i=0; i < (n); i++)


typedef long long int ll;
typedef double D;      // ??§?¨?????????????double???long double?????????
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
typedef vector<P> VP;


const int INF = (1<<30) - 1;
const D EPS = 1e-9;

#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

// ?????????dot(a,b) = |a||b|cos??
D dot(P a, P b) {
    return (conj(a)*b).X;
}
// ?????????cross(a,b) = |a||b|sin??
D cross(P a, P b) {
    return (conj(a)*b).Y;
}
// ?????????????????? a->b->c
int ccw(P a, P b, P c) {
    b -= a;	c -= a;
    //3???????????´???????????????
    if (cross(b,c) > EPS) return +1;	// counter clockwise
    if (cross(b,c) < -EPS) return -1;	// clockwise
    //3???????????´???????????????
    if (dot(b,c) < -EPS) return +2;		// c--a--b on line
    if (norm(b) < norm(c)) return -2;	// a--b--c on line or a==b
    return 0;							// a--c--b on line or a==c or b==c
}
// ????????¨??????
bool isecSS(P a1, P a2, P b1, P b2) {
    return ccw(a1, a2, b1)*ccw(a1, a2, b2) <= 0 &&
    ccw(b1, b2, a1)*ccw(b1, b2, a2) <= 0;
}
// 2????????????
VP crosspointCC(P a, D ar, P b, D br) {
    VP ps;
    P ab = b-a;
    D d = abs(ab);
    D crL = (norm(ab) + ar*ar - br*br) / (2*d);
    if (EQ(d, 0) || ar < abs(crL)) return ps;
    
    P abN = ab * P(0, sqrt(ar*ar - crL*crL) / d);
    P cp = a + crL/d * ab;
    ps.push_back(cp + abN);
    if (!EQ(norm(abN), 0)) ps.push_back(cp - abN);
    return ps;
}

class Circle{
public:
    P c;
    D r;
    Circle(D x, D y, D r){
        c = P(x, y);
        this->r = r;
    }
};

class Edge{
public:
    int to;
    D cost;
    Edge(int to, D cost): to(to), cost(cost){};
};

int N;
vector<Circle> circles;
vector<P> points;

D dijkstra(vector<vector<Edge>>& G, int s){
    int N = G.size();
    vector<D> d(N, INF);
    
    priority_queue<pair<D, int>, vector<pair<D, int>>, greater<pair<D, int>>> q;
    d[s] = 0;
    q.push(make_pair(d[s], s));
    
    while(!q.empty()){
        pair<D, int> v = q.top(); q.pop();
        if(v.first != d[v.second])
            continue;
        
        for(Edge &e: G[v.second]){
            if(e.cost + d[v.second] < d[e.to]){
                d[e.to] = e.cost + d[v.second];
                q.push(make_pair(d[e.to], e.to));
            }
        }
    }
    return d[N-1];
}

bool check(int a, int b){
    for(int i=a/2+1; i<b/2; i++){
        if(!isecSS(points[a], points[b], points[i*2], points[i*2+1]))
            return false;
    }
    return true;
}

void solve(){
    points.clear();
    
    points.push_back(circles[0].c);
    points.push_back(circles[0].c);
    for(int i=1; i<N; i++){
        Circle &c1 = circles[i-1];
        Circle &c2 = circles[i];
        auto vp = crosspointCC(c1.c, c1.r, c2.c, c2.r);
        points.push_back(vp[0]);
        points.push_back(vp[1]);
    }
    points.push_back(circles[N-1].c);
    points.push_back(circles[N-1].c);
    
    vector<vector<Edge>> G(2*N+2);
    for(int i=0; i<=N; i++){
        for(int j=i+1; j<=N; j++){
            for(int k=0; k<2; k++){
                for(int l=0; l<2; l++){
                    if(check(i*2+k, j*2+l)){
                        G[i*2+k].push_back(Edge(j*2+l, abs(points[i*2+k]-points[j*2+l])));
                    }
                }
            }
        }
    }
    
    cout << dijkstra(G, 0) << endl;
}

//g++ -std=c++0x -msse4.2 -O3
//#include <bits/stdc++.h>
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(16);
    cout.setf(ios::fixed);
    
    while (cin>>N, N) {
        circles.clear();
        for(int i=0; i<N; i++){
            D x, y, r; cin >> x >> y >> r;
            circles.push_back(Circle(x, y, r));
        }
        
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 1424