# downguardさんの回答, を改造
class Graph
  attr_accessor :vertexes

  def initialize
    @vertexes = {}
  end

  def register(index, weights)
    @vertexes[index] = Vertex.new(index, weights)
  end

  def find(index); @vertexes[index]; end

  def each; @vertexes.each{ |_, v| yield v }; end

  def prim
    min_costs = Hash.new{ | h, k | h[k] = Float::INFINITY }
    min_costs[0] = 0

    while true
      min_cost = Float::INFINITY
      selected_vertex = nil
      self.each do | v |
        if !v.selected? && min_costs[v.index] < min_cost
          selected_vertex = v
          min_cost = min_costs[v.index]
        end
      end

      break if selected_vertex.nil?

      selected_vertex.select!

      self.each do | v |
        next if v.selected? || !selected_vertex.neighbor?(v)

        if selected_vertex.cost(v) < min_costs[v.index]
          min_costs[v.index] = selected_vertex.cost(v)
          v.parent = selected_vertex
        end
      end

    end
    sum = 0
    self.each{ | v | sum += v.parent.cost(v) if v.parent }
    sum
  end

end

class Vertex
  attr_accessor :index, :parent

  def initialize(index, weights)
    # @index: 頂点を識別するindex
    # @index_cost_map: 繋がってる辺とコストの対応を示す.
    #                  {1=>2}なら頂点1にコスト2で接続.
    # @selected: 確定済み頂点か示すフラグ.
    @index = index
    @index_cost_map = weights.map.with_index{ | e, i |
      e == -1 ? nil : [i, e]
    }.compact!.to_h
    @selected = false
  end

  def neighbors(graph)
    @neighbors ||= @index_cost_map.keys.map{ | i | graph.find(i) }
  end

  def neighbor?(other)
    @index_cost_map.key?(other.index)
  end

  def cost(other)
    @index_cost_map[other.index]
  end

  def selected?;  @selected; end

  def select!; @selected = true; end

end

n = gets.to_i
graph = Graph.new
n.times do | i |
  graph.register(i, gets.split.map(&:to_i))
end

puts graph.prim

