
class Graph
  Infinity = 1000000000
  attr_accessor :size, :cost
  def initialize(size, adjacentMatrix=Array.new(n){Array.new(n)})
    @size = size
    @cost = adjacentMatrix.map(&:dup)

  end
  
  def Dijkstra(from, to)
    distance = Array.new(@size, Infinity)
    distance[from] = 0
    unused = (0...@size).to_a
    until unused.empty? do
      current = unused.sort!{|a,b| distance[a]<=>distance[b]}.shift             
      break if distance[current] == Infinity
      unused.each do |v|
        next unless @cost[current][v]
        distance[v] = [distance[v], distance[current]+@cost[current][v]].min

      end
    end

    distance[to] == Infinity ? nil : distance[to]
  end
end

EPS = 1e-10

class Class
  def ===(other)
    self==other
  end
end

class Point
  include Comparable
  attr_accessor :x, :y
  def initialize(x=0.0, y=0.0)
    @x, @y = x.to_f, y.to_f
  end

  def <=>(p)
    @x != p.x ? @x <=> p.x : @y <=> p.y
  end
  def +(p)
    Point.new(@x+p.x, @y+p.y)
  end
  def -(p)
    Point.new(@x-p.x, @y-p.y)
  end
  def -@
    Point.new(-@x, -@y)
  end

  def times(f)
    Point.new(@x*f, @y*f)
  end
  def dot(p)
    @x*p.x + @y*p.y
  end
  def cross(p)
    @x*p.y - @y*p.x
  end
  def abs
    Math::hypot(@x, @y)
  end
  def norm
    @x**2 + @y**2
  end
  
  def ccw(b, p)
    a = self
    v1, v2 = b-a, p-a
    return 1 if v1.cross(v2) > 0
    return -1 if v1.cross(v2) < 0
    return 2 if v1.dot(v2) < 0
    return -2 if v1.norm < v2.norm
    0
  end
end

class Line
  attr_accessor :a, :b
  def initialize(p1=Point.new, p2=Point.new)
    @a, @b = p1, p2
  end

  
  def ccw(p)
    v1, v2 = @b - @a, p - @a
    return 1 if v1.cross(v2) > 0
    return -1 if v1.cross(v2) < 0
    return 2 if v1.dot(v2) < 0
    return -2 if v1.norm < v2.norm
    0
  end
  
  def intersect?(target)
    case target.class
      when Point
        v1, v2 = @a-target, @b-target
        return (v2.cross(v1)).abs == 0.0
      when Segment
        v1, v2, v3 = @b-@a, target.a-@a, target.b-@a
        return v1.cross(v2) * v1.cross(v3) <= 0.0
      when Line
        v1, v2, v3 = @b-@a, target.b-target.a, target.a-@a
        return v1.cross(v2).abs > 0.0 || v1.cross(v3).abs == 0.0
    end
  end
  
  def projection(p)
    v1, v2 = p-a, a-b
    a + v2.times(v1.dot(v2)/v2.norm)
  end
  
  def reflection(p)
    p + (projection(p) - p).times(2.0)
  end
  
  def distance(target)
    case target.class
      when Point
        return (target - projection(target)).abs
      when Segment
        return intersect?(target) ? 0.0 : [distance(target.a), distance(target.b)].min
      when Line
        return intersect?(target) ? 0.0 : distance(target.a)
    end
  end
  
  def crosspoint(l)
    v1, v2, v3 = @b-@a, l.b-l.a, @b-l.a
    a, b = v1.cross(v2), v1.cross(v3)
    return l.a if a.abs == 0.0 && b.abs == 0.0
    l.a + v2.times(b/a)
  end
end

class Segment < Line
  
  def intersect?(target)
    case target.class
      when Point
        return (@a-target).abs + (@b-target).abs == (@b-@a).abs
      when Segment
        return target.ccw(@a) * target.ccw(@b) <= 0 && ccw(target.a) * ccw(target.b) <= 0
      when Line
        return target.intersect?(self)
    end
  end
  
  def distance(target)
    case target.class
      when Point
        p = projection(target)
        return intersect?(p) ? (p-target).abs : [(@a-target).abs, (@b-target).abs].min
      when Segment
        return intersect?(target) ? 0.0 : [distance(target.a), distance(target.b), target.distance(@a), target.distance(@b)].min
      when Line
        return target.distance(self)
    end
  end
end

class Circle
  include Comparable
  attr_accessor :x, :y, :r
  def initialize(x=0.0, y=0.0, r=1.0)
    @x, @y, @r = x.to_f, y.to_f, r.to_f
  end

  def <=>(c)
    @x!=c.x ? @x<=>c.x : (@y!=c.y ? @y<=>c.y : @r<=>c.r)
  end

  def point
    Point.new(@x, @y)
  end
  def distance(c)
    (point-c.point).abs
  end
  
  def include?(p)
    (point-p).abs - @r <= EPS
  end
  
  def in?(c)
    distance(c) - (@r-c.r).abs < EPS
  end
  
  def touch?(c)
    distance(c) <= @r + c.r     
  end
  
  def crossPoint(c)
    angle = Math::atan2(c.y-@y, c.x-@x)
    d = distance(c)
    add = Math::acos((d**2 + @r**2 - c.r**2) / (2.0*d*@r))
    p1 = Point.new(@x+@r*Math::cos(angle+add), @y+@r*Math::sin(angle+add))
    p2 = Point.new(@x+@r*Math::cos(angle-add), @y+@r*Math::sin(angle-add))
    [p1, p2]
  end
end

while (n = gets.to_i) != 0
  circle = Array.new
  n.times do
    circle.push(Circle.new(*gets.split.map(&:to_f)))
  end
  vertex = Array.new
  vertex.push(circle.first.point)
  gate = Array.new
  (circle.size - 1).times do |i|
    p = circle[i].crossPoint(circle[i + 1])
    gate.push(Segment.new(*p))
    vertex.push(p.pop) until p.empty?
  end
  vertex.push(circle.last.point)
  matrix = Array.new(vertex.size){Array.new(vertex.size)}
  (0...vertex.size - 1).each do |i|
    (i + 1...vertex.size).each do |j|
      edge = Segment.new(vertex[i], vertex[j])
      firstGate = (i + 1) / 2
      lastGate = (j + 1) / 2 - 1
      lastGate -= 1 if j == vertex.size - 1
      ok = true
      (firstGate..lastGate).each do |k|
        ok = false unless edge.intersect?(gate[k])
      end
      if ok
        matrix[i][j] = (vertex[i] - vertex[j]).abs
      end
    end
  end

  g = Graph.new(vertex.size, matrix)
  p g.Dijkstra(0, vertex.size - 1)
end