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: def memoize(f):
      cache = {}
  
      def helper(x):
          if x not in cache:
              cache[x] = f(x)
          return cache[x]
  
      return helper
  
  
  def split_apex(a):
      if len(a) == 2:
          yield (a[0],), (a[1],)
      else:
          for i in range(0, len(a)):
              yield (a[i],), a[:i] + a[i + 1 :]
  
  
  @memoize
  def wait(a):
      global g
      if len(a) == 1:
          return 0
      return min(calc_wait(apex, apices) for apex, apices in split_apex(a))
  
  
  def calc_wait(apex, apices):
      global g
      w = [g[apex[0]][i] for i in apices if g[apex[0]][i] != -1]
      return wait(apex) + wait(apices) + (min(w) if len(w) else 200000)
  
  
  n = int(input())
  g = [None] + [[None] + list(map(int, input().split())) for _ in range(n)]
  
  a = tuple(i + 1 for i in range(n))
  wait(a)
  
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"}]