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;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)
//#define INF (1LL<<59)

struct edge{int from,to,cost;};

class UF{
private:
	vector<int> par;
public:
	UF(int __size):par(__size){ rep(i,__size)par[i]=i; }
	
	int find(int x){
		if(par[x]==x) return x;
		else return par[x]=find(par[x]);
	}
	
	void unite(int x,int y){ par[find(y)]=find(x); }
};

int MSA(int r, int v, const vector<edge> &edges){
	int ret = 0;
	UF uf(v);
	vector<priority_queue<pii,vector<pii>,greater<pii>>> vpq(v);
	vector<int> lazy(v,0), state(v,0);
	
	for(auto e:edges){
		vpq[e.to].push(pii(e.cost,e.from));
	}
	state[r] = 2;
	
	rep(start,v){	//???????§??????????????????¨?????????
		int cur = uf.find(start);
		if(state[cur]!=0)continue;
		
		vector<int> processing, from(v,-1), from_cost(v,0);
		
		while(state[cur]!=2){
			processing.pb(cur);
			state[cur]=1;
			if( vpq[cur].empty() )return INF;	//??\?¬???°0????????????????????´????§?????????????
			
			pii e = vpq[cur].top(); vpq[cur].pop();
			from[cur] = e.second;
			from_cost[cur] = e.first+lazy[cur];
			if(cur==from[cur])continue;			//?????±??????????????????
			
			ret+=from_cost[cur];
			
			if(state[ from[cur] ]==1){	//???????????§????????¨???
				int p=cur;
				int par=cur;
				do{
					lazy[p] -= from_cost[p];
					
					if(p!=par){
						int tp=p;
						if(vpq[par].size()<vpq[tp].size())swap(par,tp);
						uf.unite(par,tp);
						while(!vpq[tp].empty()){	//?????¶?????¬????????????heap????????????
							pii t = vpq[tp].top();vpq[tp].pop();
							t.first+=lazy[tp]-lazy[par];
							vpq[par].push(t);
						}
					}
					p = from[p];
				}while(p!=cur);
				cur=par;
			}else{
				cur = from[cur];
			}
		}
		for(auto elm:processing)state[elm]=2;
	}
	return ret;
}

int main(){
	int e,v;
	int r;
	cin>>v>>e>>r;
 
	vector<edge> edges;
	rep(i,e){
		int s,t,w;
		cin>>s>>t>>w;
		edges.pb(edge{s,t,w});
	}
	cout<<MSA(r,v,edges)<<endl;
}