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).

Constraints

* 1 ≤ |V| ≤ 100
* 0 ≤ |E| ≤ 1,000
* 0 ≤ wi ≤ 10,000
* G has arborescence(s) with the root r

Input


|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.

Output

Print the sum of the weights the Minimum-Cost Arborescence.

Examples

Input

4 6 0
0 1 3
0 2 2
2 0 1
2 3 1
3 0 1
3 1 5


Output

6


Input

6 10 0
0 2 7
0 1 1
0 3 5
1 4 9
2 1 6
1 3 2
3 4 3
4 2 2
2 5 8
3 5 3


Output

11
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

#define debug() fprintf(stderr, "#%d\n", __LINE__);

template<typename T>
using RQ = std::priority_queue<T, std::vector<T>, std::greater<T>>;

struct Tree {
   Tree(Int n)
      : ps(n, -1) {}
   std::vector<Int> ps;
   Int root(Int x) {
      if( ps[x] == -1 ) return x;
      return ps[x] = root(ps[x]);
   }
   void connect(Int parent, Int child) {
      parent = root(parent), child = root(child);
      if( parent == child ) return;
      ps[root(child)] = root(parent);
   }
};

int main() {
   Int v, e, r;
   std::cin >> v >> e >> r;
   std::vector<Int> ss(e), ts(e), ws(e);
   rep(i, e) std::cin >> ss[i] >> ts[i] >> ws[i];
   std::vector<RQ<std::pair<Int,Int>>> qs(v);
   std::vector<Int> os(v);
   rep(i, e) {
      Int s = ss[i], t = ts[i], w = ws[i];
      qs[t].emplace(w, s);
   }
   std::vector<Int> xs(v);
   xs[r] = 2;
   Tree tree(v);
   bool fail = false;
   Int res = 0;
   rep(i, v) {
      fprintf(stderr, "i = %ld\n", i);
      Int a = tree.root(i);
      assert( xs[a] == 0 or xs[a] == 2 );
      guard( xs[a] == 0 );
      std::vector<std::pair<Int,Int>> ps(v);// p->i (cost, p)
      std::vector<Int> ys;
      while( xs[a] != 2 ) {
         debug();
         ys.emplace_back(a);
         xs[a] = 1;
         if( qs[a].empty() ) {
            fprintf(stderr, "fail\n");
            fail = true;
            break;
         }
         Int w, p;
         do {
            std::tie(w, p) = qs[a].top(); qs[a].pop();
         } while( tree.root(a) == tree.root(p) );
         w += os[a];
         p = tree.root(p);
         ps[a] = std::make_pair(w, p);
         res += w;
         fprintf(stderr, "res += %ld, a = %ld, p = %ld\n", w, a, p);
         if( xs[p] != 1 ) {
            a = p;
         }
         else {
            Int nr = a;
            Int b = a;
            do {
               fprintf(stderr, "b = %ld\n", b);
               if( qs[nr].size() < qs[b].size() ) nr = b;
               b = ps[b].second;
               debug();
            } while( b != a );
            fprintf(stderr, "new root = %ld\n", nr);
            fprintf(stderr, "offset of new root : %ld -> %ld\n", os[nr], os[nr]-ps[nr].first);
            os[nr] -= ps[nr].first;
            b = a;
            do {
               debug();
               if( nr != b ) {
                  tree.connect(nr, b);
                  fprintf(stderr, "connect : %ld <- %ld\n", nr, b);
                  while( not qs[b].empty() ) {
                     Int w2, p2; std::tie(w2, p2) = qs[b].top(); qs[b].pop();
                     w2 += os[b] - ps[b].first;
                     p2 = tree.root(p2);
                     Int nw = w2 - os[nr];
                     fprintf(stderr, "w2 = %ld\n", w2);
                     fprintf(stderr, "new edge : %ld -> %ld, w = %ld(prev=%ld)\n", p2, b, nw, w2);
                     qs[nr].emplace(nw, p2);
                     debug();
                  }
               }
               b = ps[b].second;
            } while( b != a );
            //    b = tree.root(ps[b].second);
            // } while( b != tree.root(a) );
            a = nr;
         }
      }
      if( fail ) break;
      for(Int y : ys) {
         xs[y] = 2;
      }
   }
   printf("%ld\n", res);
}

