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;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

struct MWA{
	using W=long long;
	using E=pair<W,int>;

	struct EHeap{
  		struct Node{
			E e; 
			W put;
			Node *l,*r;
			Node(E e):e(e),put(0),l(nullptr),r(nullptr){}
			Node* push(){
				e.first+=put;
				if(l)l->put+=put;
				if(r)r->put+=put;
				put=0;
				return this;
			}
		};
		Node* merge(Node *a,Node *b){
			if(!a)return b;
			if(!b)return a;
			a->push();b->push();
			if(a->e>b->e)swap(a,b);
			a->r=merge(a->r,b);
			swap(a->l,a->r);
			return a;
		}

		Node* root;
		EHeap():root(nullptr){}
		void pop(){
			root->push();
			root=merge(root->l,root->r);
		}
		void push(E e){
			Node *p=new Node(e);
			root=merge(root,p);
		}
		void add(W a){
			if(root)root->put+=a;
		}
		E top(){
			return root->push()->e;
		}
		void meld(EHeap &eh){
			root=merge(root,eh.root);
		}
	};

	int n;
	vector<vector<E>>G;
	MWA(int n):n(n),G(n){}

	void addEdge(int a,int b,W c){
		G[a].emplace_back(c,b);
	}

	W calc(int r){
		vector<int>par(n);iota(par.begin(),par.end(),0);
		function<int(int)>find=[&](int x){return x==par[x]?x:par[x]=find(par[x]);};
		
		vector<int>st(n);
		vector<EHeap>eh(n);
		
		rep(v,n)for(auto &e:G[v])eh[e.second].push(E(e.first,v));
		
		st[r]=2;
		W ans=0;
		rep(i,n){
			if(st[i])continue;
			int v=i;
			vector<E>es;
			
			while(st[v]!=2){
				st[v]=1;
				int u;W c;
				tie(c,u)=eh[v].top();eh[v].pop();
				u=find(u);
				if(u==v)continue;
				ans+=c;
				if(st[u]!=1){
					es.eb(c,v);
					v=u;
					continue;
				}

				eh[v].add(-c);
				while(v!=u){
					int w;
					tie(c,w)=es.back();es.pop_back();
					eh[w].add(-c);
					eh[w].meld(eh[v]);	
					par[v]=u;
					v=w;
				}
			}
			for(auto &e:es)st[e.second]=2;
		}
		return ans;
	}
};

signed main(){
	int V,E,r;
	scanf("%lld%lld%lld",&V,&E,&r);

	MWA mwa(V);
	rep(i,E){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		mwa.addEdge(a,b,c);
	}
	printf("%lld\n",mwa.calc(r));
	return 0;
}
