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"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class ConnectNodeInfo{
	vector<vector<pair<ll,ll>>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
		graph[v].emplace_back(u,w);
	}
	void AddDirectionalConnection(ll u,ll v,ll w){
		graph[u].emplace_back(v,w);
	}
	vector<pair<ll,ll>>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

ll solve(ConnectNodeInfo& connect,int R){
	int N=connect.size();
	vector<pair<ll,ll>> mins(N,make_pair(1LL<<60,-1));
	REP(i,N){
		for(auto& x:connect[i]){
			mins[x.first] = min(mins[x.first],make_pair(x.second,(ll)i));
		}
	}
	mins[R] = make_pair(-1,-1);

	vector<ll> group(N,0),comp(N,0),used(N,0);
	ll cost = 0;

	REP(i,N){
		if(used[i]) continue;
		vector<int> chain;
		int cur = i;
		while(cur!=-1 && !used[cur]){
			chain.emplace_back(cur);
			used[cur] = 1;
			cur = mins[cur].second;
		}
		if(cur!=-1){
			int cycle = 0;
			for(auto& e:chain){
				group[e] = cost;
				if(e==cur){
					cycle = 1;
					comp[cost] = 1;
				}
				if(!cycle) cost++;
			}
			if(cycle) cost++;
		}
		else{
			for(auto& e:chain){
				group[e] = cost;
				cost++;
			}
		}
	}
	if(cost==N){
		ll sum = 0;
		for(auto& x:mins) sum += x.first;
		return sum+1;
	}

	ll res = 0;
	REP(i,N){
		if(i!=R && comp[group[i]]){
			res += mins[i].first;
		}
	}

	ConnectNodeInfo new_connect(cost);
	REP(i,N){
		for(auto& x:connect[i]){
			ll gs = group[i],gt = group[x.first];
			if(gs==gt) continue;
			if(comp[gt]){
				new_connect.AddDirectionalConnection(gs,gt,x.second-mins[x.first].first);
			}
			else{
				new_connect.AddDirectionalConnection(gs,gt,x.second);
			}
		}
	}
	return res + solve(new_connect,group[R]);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N=in(),E=in(),R=in();
	ConnectNodeInfo connect(N);
	REP(i,E){
		int u=in(),v=in(),w=in();
		connect.AddDirectionalConnection(u,v,w);
	}

	out(solve(connect,R));
	return 0;
}
