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;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(a>b)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

//AOJDSL1A
//without rank
struct unionfind{
	vi p,s;
	unionfind(int n):p(n,-1),s(n,1){}
	int find(int a){
		return p[a]==-1?a:(p[a]=find(p[a]));
	}
	//set b to a child of a
	bool unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b)return false;
		p[b]=a;
		s[a]+=s[b];
		return true;
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
};

//others->root
//assume the answer exits
template<class D>
struct dirmst{
	struct E{
		int to,id;
		D cost;
		bool operator<(const E&e)const{
			//不等号の向きに注意
			return cost>e.cost;
		}
	};
	struct Q{
		using pq=priority_queue<E>;
		pq* q;
		D off;
		Q():q(new pq()),off(0){}
		~Q(){delete q;}
		void push(E e){
			q->push(e);
		}
		void merge(Q& x){
			if(q->size()<x.q->size()){
				swap(q,x.q);
				swap(off,x.off);
			}
			while(x.q->size()){
				E e=x.q->top();
				x.q->pop();
				e.cost+=x.off-off;
				q->push(e);
			}
		}
		E pop(){
			E e=q->top();
			q->pop();
			e.cost+=off;
			return e;
		}
	};
	int n,m;
	vc<Q> g;
	vi st,ci,fi,src;
	vc<D> cc;
	dirmst(int nn):n(nn),m(0),g(n),
		st(n),ci(n,-1),fi(n,-1),cc(n){}
	void ae(int s,int t,D d){
		src.pb(s);
		g[s].push({t,m++,d});
	}
	pair<D,vi> calc(int rt){
		st[rt]=2;
		vi p(m),idx;
		unionfind uf(n);
		D ans=0;
		rep(i,n)if(!st[i]){
			vi vs{i};
			st[i]=1;
			vi ch;
			while(1){
				int a=vs.back();
				E e=g[a].pop();
				cc[a]=e.cost;
				ans+=e.cost;
				ci[a]=e.id;
				if(fi[a]==-1)
					fi[a]=e.id;
				for(auto c:ch)
					p[c]=e.id;
				ch.clear();
				idx.pb(e.id);
				int to=uf.find(e.to);
				if(st[to]==0){
					vs.pb(to);
					st[to]=1;
				}else if(st[to]==1){
					int r=vs.size(),l=r-1;
					while(vs[l]!=to)
						l--;
					rng(j,l,r){
						g[vs[j]].off-=cc[vs[j]];
						if(l<j){
							g[vs[l]].merge(g[vs[j]]);
							uf.unite(vs[l],vs[j]);
						}
					}
					rng(j,l,r)
						ch.pb(ci[vs[j]]);
					vs.resize(l+1);
				}else{
					break;
				}
			}
			for(auto v:vs)
				st[v]=2;
		}
		
		vi tmp,waf(m);
		reverse(all(idx));
		for(auto i:idx)if(!waf[i]){
			tmp.pb(i);
			int x=fi[src[i]];
			while(x!=i){
				waf[x]=1;
				x=p[x];
			}
		}
		
		return make_pair(ans,tmp);
	}
};

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	
	struct E{int a,b,c;};
	int n,m,r;cin>>n>>m>>r;
	
	using ld=long double;
	dirmst<ld> dmst(n);
	const ld waf=sqrt(ld(2));
	vc<E> es;
	rep(_,m){
		int s,t,w;cin>>t>>s>>w;
		dmst.ae(s,t,w*waf);
		es.pb(E{s,t,w});
	}

	auto ans=dmst.calc(r);
	int val=round(ans.a/waf);
	assert(abs(ans.a/waf-val)<=1e-6);
	
	assert(int(ans.b.size())==n-1);
	int tot=0;
	vvc<int> ch(n);
	for(auto i:ans.b){
		tot+=es[i].c;
		ch[es[i].b].pb(es[i].a);
	}
	assert(val==tot);
	vi vis(n);
	function<void(int)> rec=[&](int v){
		assert(vis[v]==0);
		vis[v]=1;
		for(auto to:ch[v])
			rec(to);
	};
	rec(r);
	assert(find(all(vis),0)==vis.ed);
	
	cout<<val<<endl;
}

