output_description: Print the total weight of the minimum spanning tree of $G$.
input_description: In the first line, an integer $n$ denoting the number of vertices in $G$ is
  given. In the following $n$ lines, a $n \times n$ adjacency matrix $A$ which
  represents $G$ is given. $a_{ij}$ denotes the weight of edge connecting vertex
  $i$ and vertex $j$. If there is no edge between $i$ and $j$, $a_{ij}$ is given
  by -1.
attempt: import heapq
  
  
  class MST:
      """Given weighted graph, find minimum spanning tree.
  
      >>> mst = MST([[-1, 2, 3, 1, -1], \
                     [2, -1, -1, 4, -1], \
                     [3, -1, -1, 1, 1], \
                     [1, 4, 1, -1, 3], \
                     [-1, -1, 1, 3, -1]]);
      >>> mst.weight()
      5
      """
  
      MAX_WEIGHT = 2001
  
      def __init__(self, graph):
          self.graph = graph
          self.size = len(graph)
          self.tree = []
          self._search()
  
      def weight(self):
          return sum([self.graph[i][j] for i, j in self.tree])
  
      def _search(self):
          visited = [0]
  
          while len(visited) < self.size:
              h = []
              for node in visited:
                  for i, w in enumerate(self.graph[node]):
                      if w == -1:
                          continue
                      if i in visited:
                          continue
                      heapq.heappush(h, (w, node, i))
  
              weight, src, dst = heapq.heappop(h)
              visited.append(dst)
              self.tree.append((src, dst))
  
  
  def run():
      n = int(input())
  
      nodes = []
      for _ in range(n):
          nodes.append([int(i) for i in input().split()])
  
      mst = MST(nodes)
      print(mst.weight())
  
  
  if __name__ == "__main__":
      run()
  
problem_description: Minimum Spanning Tree
  
  For a given weighted graph $G = (V, E)$, find the minimum spanning tree (MST)
  of $G$ and print total weight of edges belong to the MST.
samples: [{"input": "5\n     -1 2 3 1 -1\n     2 -1 -1 4 -1\n     3 -1 -1 1 1\n     1 4 1 -1 3\n     -1 -1 1 3 -1", "output": "5"}]