class Graph
  class Node
    attr_accessor :nid, :edges, :cost, :from_nid, :fixed
    
    def initialize(nid, edges=[], cost=nil, from_nid=nil, fixed=false)
      @nid, @edges, @cost, @from_nid, @fixed = nid, edges, cost, from_nid, fixed
    end
 
    def show
      p "#{nid}(#{cost}/#{from_nid}/#{fixed}) -> #{edges}"
    end
  end
 
  def initialize
    @nodes = {}
  end
 
  def add_node(nid, edges)
    n = Node.new(nid, edges)
    @nodes[nid] = n
  end
 
  def set_start(sid)
    @sid = sid
 
    @nodes.each do |nid, node|
      node.cost = (@sid == nid) ? 0 : nil
      node.from_nid = nil
      node.fixed = false
    end
 
    dijkstra
  end
 
  def route(gid)
    path = []
 
    node = @nodes[gid]
    path.push(node)
 
    loop do
      node = @nodes[node.from_nid]
      path.push(node)
 
      break if node.nid == @sid
 
      return nil if node.from_nid.nil?
    end
  
    return path.reverse!.map { |node| node.nid }
  end
 
  def cost(gid)
    return @nodes[gid].cost
  end
 
  def show
    @nodes.map { |k, node| node.show } 
  end
 
private
  def dijkstra
    loop do
      fixed_node = nil
      @nodes.each do |nib, node|
        next if node.fixed || node.cost.nil?
        fixed_node = node if fixed_node.nil? || node.cost < fixed_node.cost
      end
 
      break if fixed_node.nil?
 
      fixed_node.fixed = true
      fixed_node.edges.each do |edge_cost, edge_nid|
        cost = fixed_node.cost + edge_cost
        if @nodes[edge_nid].cost.nil? || cost < @nodes[edge_nid].cost then
          @nodes[edge_nid].cost = cost
          @nodes[edge_nid].from_nid = fixed_node.nid
        end
      end
    end
  end
 
end

xy = gets.chomp.split(" ").map(&:to_i)
n = gets.chomp.split(" ").map(&:to_i)
list = []

def euc_dis(a,b,c,d)
  return Math.sqrt((a-c)**2 + (b-d)**2)
end

end_circle = nil
fst_circle = nil
dist_array = Array.new(n[0]+2).map{Array.new(n[0]+2, 0)}
n0 = n[0]
n[0].times do |i|
  t = gets.chomp.split(" ").map(&:to_i)
  k = euc_dis(xy[0], xy[1], t[0], t[1]) - t[2]
  k2 = euc_dis(xy[2], xy[3], t[0], t[1]) - t[2]
  dist_array[i][n0]=k if k > 0#euc_dis(xy[0], xy[1], t[0], t[1]) - t[2]
  dist_array[i][n0+1]=k2 if k2 > 0#euc_dis(xy[2], xy[3], t[0], t[1]) - t[2]
  dist_array[n0][i]=k if k > 0#euc_dis(xy[0], xy[1], t[0], t[1]) - t[2]
  dist_array[n0+1][i]=k2 if k2 > 0#euc_dis(xy[2], xy[3], t[0], t[1]) - t[2]
  end_circle = i if !end_circle || t[-1] < list[end_circle][-1] 
  fst_circle = i if !fst_circle || t[-2] < list[fst_circle][-2] 

  min_dist = 0
  list.map{|ta| euc_dis(ta[0], ta[1], t[0], t[1]) - t[2] - ta[2]}.each_with_index do |item, j|
    dist_array[i][j] = item if item > 0
    dist_array[j][i] = item if item > 0
    #min_dist = item if item < min_dist
  end
  #if xy[0] <= t[0] && t[0] <= xy[2] && xy[1] <= t[1] && t[1] <= xy[3]
    list << t
  #end
end
  #list[end_circle][-1] = 0 if list[end_circle][-1] < 0
  #list[fst_circle][-2] = 0 if list[fst_circle][-2] < 0
=begin
if end_circle == fst_circle
  val = list[end_circle][-1] + list[end_circle][-2]
  if val > euc_dis(xy[0], xy[1], xy[2], xy[3])
  p euc_dis(xy[0], xy[1], xy[2], xy[3])
  else
  p val
  end
  exit
end
=end
dist_array[n0][n0+1] = euc_dis(xy[0], xy[1], xy[2], xy[3])
dist_array[n0+1][n0] = euc_dis(xy[0], xy[1], xy[2], xy[3])

g = Graph.new
 
  dist_array.each_with_index do |edges, nid|
    edges = edges.map.with_index {|t,i| [t, i]}
    g.add_node(nid, edges)
  end
  #g.add_node(: list.map.with_index{|ta, i| [i, ta[4]]}
  g.set_start(n[0])
 
  val = list[end_circle][-1] + list[fst_circle][-2] 
  val = g.cost(n[0]+1) 
  #val1 = list[end_circle][-1] + list[fst_circle][-2] #+ g.cost(fst_circle) 
  if val > euc_dis(xy[0], xy[1], xy[2], xy[3])
  p euc_dis(xy[0], xy[1], xy[2], xy[3])
  else
  p val
  end


Measured memory_bytes: 58108