INF = 0x7fffffff

def prim(g, n)
  d = Array.new(n, INF)
  pi = Array.new(n, -1)
  color = Array.new(n, 0)
  
  d[0] = 0  
  sum = 0
  loop do
    u = -1
    mincost = INF
    (0...n).each do |i|
      if mincost > d[i] && color[i] != 2
        u = i
        mincost  = d[i]
      end
    end
    break if u == -1
    color[u] = 2
    
    (0...n).each do |i|
      if color[i] != 2 && d[i] > g[u][i] && g[u][i] != INF
          d[i] = g[u][i]
          pi[i] = u
          color[i] = 1
      end
    end
  end
  (0...n).each do |j|
    sum += g[j][pi[j]] unless pi[j] == -1
  end
  return sum
end

n = gets.to_i
g = Array.new(n) { Array.new(n) }

(0...n).each do |i|
  g[i] = gets.split.map(&:to_i)
  (0...n).each do |j|
    g[i][j] = INF if g[i][j] == -1
  end
end
puts prim(g, n)