@a = nil
@n = nil

def prim
  d = Array.new(@n, Float::INFINITY)
  color = Array.new(@n, "WHITE")
  p = []
  d[0] = 0
  p[0] = -1
  u = nil

  while true
    mincost = Float::INFINITY
    (0..@n-1).each do |i|
      if color[i] != "BLACK" && d[i] < mincost
        mincost = d[i]
        u = i
      end
    end

    break if mincost == Float::INFINITY

    color[u] = "BLACK"

    (0..@n-1).each do |v|
      if color[v] != "BLACK" && @a[u][v] != -1
        if @a[u][v] < d[v]
          d[v] = @a[u][v]
          p[v] = u
          color[v] = "GLAY"
        end
      end
    end
  end

  return d.reduce { |sum, i| i == Float::INFINITY ? 0 : sum + i }
end

def main
  @n = gets.to_i
  @a = Array.new(@n).map { Array.new(@n, nil) }
  (0..@n-1).each do |i|
    @a[i] = gets.split.map { |j| j.to_i }
  end
  puts prim
end

main