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<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct edge{
  int v,w;
};

vector<int> minimum_spanning_arborescence(const vector<vector<edge> > &G,int root){
  const int INF=1<<29;
  const int N=G.size();
  // cout<<"N = "<<N<<endl;
  // for(int i=0;i<N;i++){
  //   for(auto e:G[i]){
  //     cout<<i<<' '<<e.v<<' '<<e.w<<endl;
  //   }
  // }

  vector<int> prev(N,-1),weight(N,INF);
  for(int i=0;i<N;i++){
    for(auto e:G[i]){
      if(e.v!=root&&e.w<weight[e.v]){
	weight[e.v]=e.w;
	prev[e.v]=i;
      }
    }
  }
  vector<int> check(N,N);
  vector<int> cycle;
  vector<char> in_cycle(N);
  for(int i=0;i<N;i++){
    for(int j=i;j>=0;){
      if(check[j]<i)break;
      if(check[j]==i){
	for(int k=j;;){
	  cycle.push_back(k);
	  in_cycle[k]=true;
	  k=prev[k];
	  if(k==j)goto found;
	}
      }
      check[j]=i;
      j=prev[j];
    }
  }
  return prev;
 found:
  int nN=N-cycle.size()+1;
  vector<int> newv(N),oldv(N);
  for(int i=0,idx=0;i<N;i++){
    if(!in_cycle[i]){
      oldv[idx]=i;
      newv[i]=idx++;
    }else{
      newv[i]=nN-1;
    }
  }
  vector<vector<edge> > nG(nN);
  vector<int> in(N,-1),out(N,-1);
  vector<int> in_val(N,INF),out_val(N,INF);
  for(int i=0;i<N;i++){
    for(auto e:G[i]){
      int nc=e.w-weight[e.v];
      if(!in_cycle[i]){
	if(!in_cycle[e.v]){
	  nG[newv[i]].push_back({newv[e.v],nc});
	}else{
	  if(nc<in_val[i]){
	    in_val[i]=nc;
	    in[i]=e.v;
	  }
	}
      }else{
	if(!in_cycle[e.v]){
	  if(nc<out_val[e.v]){
	    out_val[e.v]=nc;
	    out[e.v]=i;
	  }
	}
      }
    }
  }
  for(int i=0;i<N;i++){
    if(in_val[i]<INF){
      nG[newv[i]].push_back({nN-1,in_val[i]});
    }
    if(out_val[i]<INF){
      nG[nN-1].push_back({newv[i],out_val[i]});
    }
  }
  auto r=minimum_spanning_arborescence(nG,newv[root]);
  vector<int> rv(N);
  for(int i=0;i<nN-1;i++){
    if(r[i]<0){
      rv[oldv[i]]=r[i];
    }else if(r[i]<nN-1){
      rv[oldv[i]]=oldv[r[i]];
    }else{
      rv[oldv[i]]=out[oldv[i]];
    }
  }
  int v_into_cycle=oldv[r[nN-1]];
  int v_in_cycle=in[v_into_cycle];
  rv[v_in_cycle]=v_into_cycle;
  int x=prev[v_in_cycle];
  for(int i=0;i<cycle.size()-1;i++){
    rv[x]=prev[x];
    x=prev[x];
  }
  return rv;
}

int main(){
  int V,E,r;
  cin>>V>>E>>r;
  vector<vector<edge> > G(V);
  for(int i=0;i<E;i++){
    int s,t,w;
    cin>>s>>t>>w;
    G[s].push_back({t,w});
  }
  auto msa=minimum_spanning_arborescence(G,r);
  for(auto e:msa){
    //    cout<<e<<endl;
  }
  int ans=0;
  for(int i=0;i<G.size();i++){
    for(auto e:G[i]){
      if(msa[e.v]==i){
	ans+=e.w;
      }
    }
  }
  cout<<ans<<endl;
}