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 namespace std;

struct union_find{
  vector<int> par;
  union_find(){}
  union_find(int n){
    par.resize(n);
    iota(par.begin(),par.end(),0);
  }
  int root(int k){
    if(par[k]==k)return k;
    return par[k] = root(par[k]);
  }
  void unite(int a,int b){
    a = root(a);
    b = root(b);
    if(a==b)return;
    par[a] = b;
  }
};
template<class T>
struct node{
  T val;
  T lazy;
  int id;
  node<T>* left;
  node<T>* right;
  node():left(nullptr),right(nullptr){}
  node(T& v,int i):val(v),lazy(0),left(nullptr),right(nullptr),id(i){}
};
template<class T>
struct skew_heap{
  node<T>* root;
  size_t sz;
  skew_heap():root(nullptr),sz(0){}
  skew_heap(T& v,int i){
    root = new node<T>(v,i);
    sz = 1;
  }
private:
  void lazy(node<T>* n){
    n->val += n->lazy;
    if(n->left)n->left->lazy += n->lazy;
    if(n->right)n->right->lazy += n->lazy;
    n->lazy = 0;
  }
  node<T>* meld(node<T>* a,node<T>* b){
    if(!a)return b;
    if(!b)return a;
    if( a->val+a->lazy > b->val+b->lazy )std::swap(a,b);
    lazy(a);
    a->right = meld(a->right,b);
    std::swap(a->left,a->right);
    return a;
  }
public:
  node<T> top(){
    assert(!empty());
    lazy(this->root);
    node<T> r(root->val,root->id);
    return r;
  }
  void pop(){
    assert(!empty());
    free(root);
    root = meld(root->right,root->left);
    sz--;
  }
  void push(T v,int i){
    skew_heap<T> tmp(v,i);
    this->meld(tmp);
  }
  void add(T v){
    this->root->lazy += v;
  }
  void meld(skew_heap& h){
    this->root = meld(this->root,h.root);
    this->sz += h.sz;
    h.sz = 0;
    h.root = nullptr;
  }
  bool empty()const{
    return sz==0;
  }
  size_t size()const{
    return this->sz;
  }
};

template<class cost_t>
struct edge{
  int from,to;
  cost_t cost;
  edge(){}
  edge(int f,int t,cost_t c):from(f),to(t),cost(c){}
};

template<class cost_t>
struct MSA{
  union_find uni;
  vector<skew_heap<cost_t>> come;
  vector<edge<cost_t>> edges;
  vector<int> used,from_cost,from;
  int n,r;
  MSA(){}
  MSA(vector<edge<cost_t>> const& e,int n,int r=0):edges(e),n(n),r(r){
    uni = union_find(n);
    come.resize(n);
    used = from_cost = from = vector<int>(n);
  }
  cost_t calc(){
    used[r] = 2;
    for(int i=0;i<edges.size();++i){
      auto& e = edges[i];
      come[e.to].push(e.cost,i);
    }
    cost_t result = 0;
    for(int s=0;s<n;++s){
      if(used[s]!=0)continue;
      int cur = s;
      vector<int> processing;
      while(used[cur]!=2){
        used[cur] = 1;
        processing.emplace_back(cur);
        if(come[cur].empty())return numeric_limits<cost_t>::max();
        from[cur] = uni.root(edges[come[cur].top().id].from);
        from_cost[cur] = come[cur].top().val;
        come[cur].pop();
        if(from[cur]==cur)continue;
        result += from_cost[cur];
        if(used[from[cur]]==1){
          int p = cur;
          do{
            if(!come[p].empty())come[p].add(-from_cost[p]);
            if(p!=cur){
              uni.unite(p,cur);
              come[cur].meld(come[p]);
            }
            p = uni.root(from[p]);
          }while(p!=cur);
        }else{
          cur = from[cur];
        }
      }
      for(int v:processing){
        used[v] = 2;
      }
    }
    return result;
  }
};

signed main(){

  int v,e,r;
  cin>>v>>e>>r;
  vector<edge<int64_t>> edges;
  for(int i=0;i<e;++i){
    int s,t,w;
    cin>>s>>t>>w;
    edges.emplace_back(s,t,w);
  }
  MSA<int64_t> g(edges,v,r);
  cout<< g.calc() <<endl;

}
