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 <climits>
using namespace std;
#define fr second.first
#define to second.second
#define co first
const int INF=INT_MAX;
typedef pair<int,int> P;
typedef pair<int,P> Edge;
long long edmonds(vector<Edge> edges,int v,int st) {
 
  vector<P> mins(v,P(INF,-1));
  for(int i=0;i<(int)edges.size();i++) {
    Edge edge=edges[i];
    mins[edge.to]=min(mins[edge.to],P(edge.co,edge.fr));
  }
  mins[st]=P(-1,-1);
  
  vector<int> gr(v,0);
  vector<bool> tfc(v,false),f(v,false);
  int cnt=0; 

  for(int i=0;i<v;i++){
    if(f[i]) continue;
    vector<int> ch;
    int cu=i;
    for(;cu!=-1&&!f[cu];){ 
      f[cu]=true;
      ch.push_back(cu);
      cu=mins[cu].second;
    }
    if(cu!=-1){
      bool tfc2=false;
      for(int j=0;j<(int)ch.size();j++) {
	gr[ch[j]]=cnt;
	if(ch[j]==cu){
	  tfc[cnt]=true;
	  tfc2=true;
	}
	if(!tfc2) cnt++;
      }
      if(tfc2) cnt++;
    }
    else for(int j=0;j<(int)ch.size();j++,cnt++) gr[ch[j]]=cnt;
  }

  if(cnt==v){
    long long ans=1;
    for(int i=0;i<v;i++) ans+=mins[i].co;
    return ans;
  }

  long long res=0;
  for(int i=0;i<v;i++) if(i!=st&&tfc[gr[i]]) res+=mins[i].co;
    
  vector<Edge> nedges;
  for(int i=0;i<(int)edges.size();i++) {
    Edge edge=edges[i];
    int fto=edge.to,gfr=gr[edge.fr],gto=gr[edge.to];
    if(gfr==gto) continue;
    else if(tfc[gto]) nedges.push_back(make_pair(edge.co-mins[fto].co,P(gfr,gto)));
    else nedges.push_back(make_pair(edge.co,P(gfr,gto)));
  }

  return res+edmonds(nedges,cnt,gr[st]);

}

int main(){
  int v,e,r;
  cin>>v>>e>>r;
  vector<Edge> es;
  for(int i=0,s,t,w;i<e&&cin>>s>>t>>w;i++) es.push_back(make_pair(w,P(s,t)));
  cout<<edmonds(es,v,r)<<endl;
  return 0;
}