import math


class Vec:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __mul__(self, other):
        return Vec(self.x * other, self.y * other)

    def length(self):
        return math.sqrt(self.x * self.x + self.y * self.y)

    def __str__(self):
        return "({},{})".format(self.x, self.y)

    def __sub__(self, other):
        return Vec(self.x - other.x, self.y - other.y)

    def __add__(self, other):
        return Vec(self.x + other.x, self.y + other.y)

    def __truediv__(self, other):
        return Vec(self.x / other, self.y / other)

    def turn90(self):
        return Vec(-self.y, self.x)

    def normalized(self):
        return self / self.length()

    def is_clock(self, other):
        return self.x * other.y - self.y * other.x < 0


class Circle:
    def __init__(self, x, y, r):
        self.r = r
        self.center = Vec(x, y)

    def intersection(self, other):
        d = (self.center - other.center).length()
        r1 = self.r
        r2 = other.r
        d1 = (d * d + r1 * r1 - r2 * r2) / 2 / d
        x = math.sqrt(r1 * r1 - d1 * d1)
        e1 = (other.center - self.center).normalized()
        e2 = e1.turn90()

        p1 = self.center + e1 * d1 + e2 * x
        p2 = self.center + e1 * d1 - e2 * x
        return p1, p2

    def __str__(self):
        return "({},{})".format(self.center, self.r)


def solve(ps: [Circle]):
    intersects = []
    for i in range(len(ps) - 1):
        ci = ps[i]
        ci_next = ps[i + 1]
        intersection1, intersection2 = ci.intersection(ci_next)
        intersects.append((intersection1, intersection2))

    res = [[ps[0].center, -1, 0]]  # 候補座標とその深度と左右(0,1)
    dists = [[2 ** 32, 2 ** 32] for _ in range(len(intersects))]  # 各交点の距離バッファ

    min_path_length = 2 ** 32

    while len(res) != 0:
        res = sorted(res, key=lambda a: a[1], reverse=True)

        c, depth, lr = res.pop()
        current_path_length = dists[depth][lr] if depth != -1 else 0
        if depth == len(intersects) - 1:
            last_path = ps[-1].center - c
            min_path_length = min(min_path_length, current_path_length + last_path.length())
            continue

        l_limit_min, r_limit_min = [a - c for a in intersects[depth + 1]]  # 左右の限界
        l_limit, r_limit = l_limit_min, r_limit_min  # 到達可能限界
        l_limit_d, r_limit_d = depth + 1, depth + 1

        flag = True
        for i in range(depth + 2, len(intersects)):
            l_limit2, r_limit2 = [a - c for a in intersects[i]]

            if l_limit_min.is_clock(l_limit2):  # 限界更新
                l_limit_min = l_limit2
                if l_limit2.is_clock(r_limit_min):  # 到達可能なら、こっちも更新
                    l_limit = l_limit2
                    l_limit_d = i
            if r_limit2.is_clock(r_limit_min):  # 限界更新
                r_limit_min = r_limit2
                if l_limit_min.is_clock(r_limit2):  # 到達可能なら、こっちも更新
                    r_limit = r_limit2
                    r_limit_d = i
            if r_limit_min.is_clock(l_limit_min):
                flag = False
                break
        last_path = ps[-1].center - c
        if flag and l_limit_min.is_clock(last_path) and last_path.is_clock(r_limit_min):  # この点からゴールまで行ける
            min_path_length = min(min_path_length, current_path_length + last_path.length())
            continue
        if dists[l_limit_d][0] > l_limit.length() + current_path_length:
            dists[l_limit_d][0] = l_limit.length() + current_path_length
            res.append([l_limit + c, l_limit_d, 0])
        if dists[r_limit_d][1] > r_limit.length() + current_path_length:
            dists[r_limit_d][1] = r_limit.length() + current_path_length
            res.append([r_limit + c, r_limit_d, 1])
    return min_path_length


def main():
    while True:
        n = int(input())
        if n == 0:
            break

        ps = [Circle(*[int(a) for a in input().split()]) for _ in range(n)]

        print(solve(ps))


if __name__ == '__main__':
    main()



Measured memory_bytes: 5836