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: # Edige Weighted Digraph
  
  
  from collections import namedtuple
  
  
  WeightedEdge = namedtuple("WeightedEdge", ("src", "dest", "weight"))
  
  
  class Digraph:
      def __init__(self, v):
          self.v = v
          self._edges = [[] for _ in range(v)]
  
      def add(self, edge):
          self._edges[edge.src].append(edge)
  
      def adj(self, v):
          return self._edges[v]
  
      def edges(self):
          for es in self._edges:
              for e in es:
                  yield e
  
  
  def mca_chu_liu_edmonds(graph, s):
      def select_edges():
          es = [None] * graph.v
          for v in range(graph.v):
              for e in graph.adj(v):
                  w = e.dest
                  if w == s:
                      continue
                  if es[w] is None or e.weight < es[w].weight:
                      es[w] = e
          return es
  
      def find_cycle(es):
          vs = [0 for _ in range(graph.v)]
          for e in es:
              if e is None:
                  continue
              vs[e.src] += 1
          leaves = [v for v, c in enumerate(vs) if c == 0]
          while leaves:
              leaf, *leaves = leaves
              if es[leaf] is not None:
                  w = es[leaf].src
                  vs[w] -= 1
                  if vs[w] == 0:
                      leaves.append(w)
          cycle = []
          for v, c in enumerate(vs):
              if c > 0:
                  cycle.append(v)
                  u = es[v].src
                  while u != v:
                      cycle.append(u)
                      u = es[u].src
                  break
          return cycle
  
      def contract(es, vs):
          vvs = []
          vv = 0
          c = graph.v - len(vs)
          for v in range(graph.v):
              if v in vs:
                  vvs.append(c)
              else:
                  vvs.append(vv)
                  vv += 1
          g = Digraph(c + 1)
          for v in range(graph.v):
              for e in graph.adj(v):
                  if e.src not in vs or e.dest not in vs:
                      v = vvs[e.src]
                      w = vvs[e.dest]
                      weight = e.weight
                      if e.dest in vs:
                          weight -= es[e.dest].weight
                      e = WeightedEdge(v, w, weight)
                      g.add(e)
          return g, vvs[s]
  
      edges = select_edges()
      cycle = find_cycle(edges)
  
      if cycle:
          g, ss = contract(edges, cycle)
          return mca_chu_liu_edmonds(g, ss) + sum(edges[v].weight for v in cycle)
      else:
          return sum(e.weight for e in edges if e is not None)
  
  
  def run():
      v, e, r = [int(i) for i in input().split()]
      graph = Digraph(v)
  
      for _ in range(e):
          s, t, w = [int(i) for i in input().split()]
          graph.add(WeightedEdge(s, t, w))
  
      print(mca_chu_liu_edmonds(graph, r))
  
  
  if __name__ == "__main__":
      run()
  
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"}]