import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def _kosa(a1, a2, b1, b2):
    x1,y1 = a1
    x2,y2 = a2
    x3,y3 = b1
    x4,y4 = b2

    tc = (x1-x2)*(y3-y1)+(y1-y2)*(x1-x3)
    td = (x1-x2)*(y4-y1)+(y1-y2)*(x1-x4)
    return tc*td < 0

def kosa(a1, a2, b1, b2):
    return _kosa(a1,a2,b1,b2) and _kosa(b1,b2,a1,a2)

def distance(x1, y1, x2, y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

def distance_p(a, b):
    return distance(a[0], a[1], b[0], b[1])

def polar(a, r):
    return (math.cos(r) * a, math.sin(r) * a)

def intersection_c(ap, bp):
    ax,ay,ar = ap
    bx,by,br = bp
    d = distance(ax,ay,bx,by)
    if d > ar + br or d < abs(ar - br):
        return None

    ac = math.acos((ar**2 + d**2 - br**2) / (2 * ar * d))
    t = math.atan2(by - ay, bx - ax)
    r1 = polar(ar, t + ac)
    r2 = polar(ar, t - ac)
    return [(ax+r1[0], ay+r1[1]), (ax+r2[0], ay+r2[1])]

def main():
    rr = []

    def f(n):
        a = [LI() for _ in range(n)]
        inters = []
        for i in range(n-1):
            inters.append(intersection_c(a[i], a[i+1]))
        dp = [[inf]*2 for _ in range(n-1)]
        s = a[0][:2]
        rt = a[-1][:2]
        rf = True
        for k in range(n-1):
            if not kosa(s,rt,inters[k][0],inters[k][1]):
                rf = False
                break
        if rf:
            return distance_p(s,rt)

        for i in range(n-1):
            for j in range(2):
                t = inters[i][j]
                f = True
                for k in range(i):
                    if not kosa(s,t, inters[k][0], inters[k][1]):
                        f = False
                        break
                if f:
                    dp[i][j] = distance_p(s,t)

        r = inf
        # print('dp', dp)
        for i in range(n-1):
            for j in range(2):
                s = inters[i][j]
                sd = dp[i][j]
                for k in range(i+1,n-1):
                    for l in range(2):
                        t = inters[k][l]
                        f = True
                        for m in range(i+1,k):
                            if not kosa(s,t,inters[m][0], inters[m][1]):
                                f = False
                                break
                        # print('s,t,f',s,t,f)
                        if f:
                            nd = sd + distance_p(s,t)
                            if dp[k][l] > nd:
                                dp[k][l] = nd
                t = a[-1][:2]
                f = True
                for k in range(i+1,n-1):
                    if not kosa(s,t,inters[k][0], inters[k][1]):
                        f = False
                        break
                if f:
                    nd = sd + distance_p(s,t)
                    if r > nd:
                        r = nd
            # print('i',i,inters[i])
            # print('dp', dp)
            # print('r', r)
        return '{:0.5f}'.format(r)

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str,rr))


print(main())



Measured memory_bytes: 9272