output_description: Print the sum of the weights the Minimum-Cost Arborescence.
input_description: |V| |E| r
      s0 t0 w0
      s1 t1 w1
      :
      s|E|-1 t|E|-1 w|E|-1
      
  
  , where |V| is the number of vertices and |E| is the number of edges in the
  graph. The graph vertices are named with the numbers 0, 1,..., |V|-1
  respectively. r is the root of the Minimum-Cost Arborescence.
  
  si and ti represent source and target verticess of i-th directed edge. wi
  represents the weight of the i-th directed edge.
attempt: # Acceptance of input
  
  import sys
  
  file_input = sys.stdin
  
  v_num, e_num, r = map(int, file_input.readline().split())
  
  G = [[] for i in range(v_num)]
  
  import heapq
  
  for line in file_input:
      s, t, w = map(int, line.split())
      if t != r:
          heapq.heappush(G[t], [w, s, t])
  
  # Edmonds' algorithm
  
  
  def find_cycle(incoming_edges, root):
      in_tree = [False] * v_num
      in_tree[root] = True
      for e in incoming_edges[:root] + incoming_edges[root + 1 :]:
          S = []
          S.append(e[2])
          while True:
              p = incoming_edges[S[-1]][1]
              if in_tree[p]:
                  while S:
                      in_tree[S.pop()] = True
                  break
              elif p in S:
                  return S[S.index(p) :]  # return nodes in a cycle
              else:
                  S.append(p)
      return None
  
  
  def contract_cycle(digraph, cycle_node):
      for edges in digraph:
          min_weight = edges[0][0]
          for e in edges:
              e[0] -= min_weight
      contracted_edges = []
      for n in cycle_node:
          edge_set_in_cycle = digraph[n]
          heapq.heappop(edge_set_in_cycle)
          for e in edge_set_in_cycle:
              heapq.heappush(contracted_edges, e)
      for n in cycle_node:
          digraph[n] = contracted_edges
  
  
  def edmonds_branching(digraph, root, weight):
      min_incoming_edges = [None] * v_num
      for edges in digraph[:root] + digraph[root + 1 :]:
          min_edge = edges[0]
          min_incoming_edges[min_edge[2]] = min_edge
          weight += min_edge[0]
      C = find_cycle(min_incoming_edges, root)
      if not C:
          return weight
      else:
          contract_cycle(digraph, C)
          return edmonds_branching(digraph, root, weight)
  
  
  # output
  print(edmonds_branching(G, r, 0))
  
problem_description: Minimum-Cost Arborescence
  
    
  
  Find the sum of the weights of edges of the Minimum-Cost Arborescence with the
  root r for a given weighted directed graph G = (V, E).
samples: [{"input": "4 6 0\n    0 1 3\n    0 2 2\n    2 0 1\n    2 3 1\n    3 0 1\n    3 1 5", "output": "6"}, {"input": "6 10 0\n    0 2 7\n    0 1 1\n    0 3 5\n    1 4 9\n    2 1 6\n    1 3 2\n    3 4 3\n    4 2 2\n    2 5 8\n    3 5 3", "output": "11"}]