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;

//Chu_Liu_Edmonds
typedef pair<int,int> point;
typedef pair<int,point> edge;

#define inf 1e9

int solve(vector<edge> &g,int v,int r){
	vector<point> mins(v,point(inf,-1));
	for(int i=0;i<g.size();i++){
		edge tmp = g[i];
		point p = tmp.second;
		mins[p.second]  =  min(mins[p.second],point(tmp.first,p.first));
	}
	mins[r] = point(-1,-1);	
	vector<int> grop(v,0);
	vector<bool> cycle(v,false);
	int cnt=0;
	
	vector<bool> used(v,false);
	for(int i=0;i<v;i++){
		if(used[i])continue;
		vector<int> chain;
		int now = i;
		while(now !=-1&&!used[now]){
			//元を辿る
			used[now]= true;
			chain.push_back(now);
			now = mins[now].second;
		}
		if(now !=-1){
			bool incycle = false;
			for(int j=0;j<chain.size();j++){
				grop[chain[j]]=cnt;
				if(chain[j]==now){
					cycle[cnt] = true;
					incycle = true;
				}
				if(!incycle)cnt++;
			}
		 if(incycle)cnt++;
		}else{
			for(int j=0;j<chain.size();j++){
					grop[chain[j]] = cnt;
					cnt++;
			}	
		}

	}
	if(cnt==v){
		//because root is -1 
		int ans =1;
		for(int i=0;i<v;i++)ans+=mins[i].first;
		return ans;
	}
	int res = 0;
	for(int i=0;i<v;i++){
		if(i != r && cycle[grop[i]])res += mins[i].first;
	}
	//cycle exist ,so make new graph
	vector<edge> newg;
	for(int i=0;i<g.size();i++){
		edge e = g[i];
		point p = e.second;
		int to = p.second;
		int gfrom = grop[p.first];
		int gto = grop[p.second];
		if(gfrom ==gto)continue;
		else if(cycle[gto])	newg.push_back(edge(e.first-mins[to].first,point(gfrom,gto)) );
		else 	newg.push_back(edge(e.first,point(gfrom,gto) ) );
	}
	return res + solve(newg,cnt,grop[r]);
}


int main(){
	int v,e,r;
	cin>>v>>e>>r;
	vector<edge> g;
	for(int i=0;i<e;i++){
		int s,t,w;
		cin>>s>>t>>w;
		point p = point(s,t);
		g.push_back( edge(w,p) );
	}
	cout<<solve(g,v,r)<<endl;
	return 0;
}
