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<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
class SCC{//cmp(0 - kk-1) is scc's return. Same number is group. The number is no relatoin.
	public:
	int n;
	vvi G;
	vvi rG;
	vector<bool>used;
	vi vs;
	vi cmp;
	SCC(int size){
		n=size;
		G=rG=vvi(n);
		used=vector<bool>(n);
		cmp=vi(n);
		vs=vi(0);
	}
	void add_edge(int s,int t){
		G[s].pb(t);
		rG[t].pb(s);
	}
	void rdfs(int v,int k){
		used[v]=true;
		cmp[v]=k;
		rep(i,rG[v].size())if(!used[rG[v][i]])rdfs(rG[v][i],k);
	}
	void dfs(int v){
		used[v]=true;
		rep(i,G[v].size())if(!used[G[v][i]])dfs(G[v][i]);
		vs.pb(v);
	}
	int scc(){
		rep(i,n)used[i]=false;
		rep(v,n)if(!used[v])dfs(v);
		rep(i,n)used[i]=false;
		int kk=0;
		for(int i=vs.size()-1;i>=0;i--)if(!used[vs[i]])rdfs(vs[i],kk++);
		return kk;  
	}
};
struct edge{
	int to,cost;
};
class MCA{
	public:
	int n,r;
	vector<vector<edge> >G,rG,tG,trG;
	vector<bool>used;
	MCA(int size,int R){
		r=R;
		n=size;
		rG=G=vector<vector<edge> >(n);
	}
	void add_edge(int s,int t,int cost){
		edge e={t,cost},ee={s,cost};
		G[s].pb(e);rG[t].pb(ee);
	}
	void dfs(int s){
		used[s]=true;
		rep(i,tG[s].size())if(!used[tG[s][i].to])dfs(tG[s][i].to);
	}
	int mca(){
		tG=trG=vector<vector<edge> >(n);
		rep(i,n)if(i!=r){
			int mi=inf;
			rep(j,rG[i].size())mi=min(mi,rG[i][j].cost);
			rep(j,rG[i].size())if(mi==rG[i][j].cost){
				edge e={i,rG[i][j].cost};
				tG[rG[i][j].to].pb(e);
				trG[i].pb(rG[i][j]);
				break;
			}
		}
//		rep(i,n)rep(j,trG[i].size())cout<<i<<" "<<trG[i][j].to<<" "<<trG[i][j].cost<<endl;
		used=vector<bool>(n);
		dfs(r);
		bool h=true;
		rep(i,n)if(!used[i])h=false;
		if(h){//connect
			int sum=0;
			rep(i,n)rep(j,tG[i].size())sum+=tG[i][j].cost;
			return sum;		
		}else{// not connect
			SCC scc(n);
			rep(i,n)rep(j,tG[i].size())scc.add_edge(i,tG[i][j].to);
			int N=scc.scc();
			MCA mca(N,scc.cmp[r]);
			int sum=0;
			rep(i,n)rep(j,tG[i].size())if(scc.cmp[i]==scc.cmp[tG[i][j].to])sum+=tG[i][j].cost;
			rep(i,n)rep(j,G[i].size())if(scc.cmp[i]!=scc.cmp[G[i][j].to]){
				bool h=false;
				int To=G[i][j].to;//i -> To
				rep(k,n)if(To!=k&&scc.cmp[To]==scc.cmp[k])h=true;
				if(h){
					mca.add_edge(scc.cmp[i],scc.cmp[To],G[i][j].cost-trG[To][0].cost);
				}else{
					mca.add_edge(scc.cmp[i],scc.cmp[To],G[i][j].cost);
				}
			}
//			rep(i,N)rep(j,mca.G[i].size())cout<<i<<" "<<mca.G[i][j].to<<" "<<mca.G[i][j].cost<<endl;
			return sum+mca.mca();
		}
		return false;
	}
};
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	MCA mca(n,k);
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		mca.add_edge(a,b,c);
	}
	cout<<mca.mca()<<endl;
}
 


 
 