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<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

/*
最小有向全域木
Chu-Liu/Edmonds' algorithm

//参考　https://ark4rk.hatenablog.com/entry/2017/09/15/011937

*/

constexpr int INF = 1e9;

bool cycle_detection(const vector<vector<int>> &G, vector<bool> &used, vector<bool> &used2, deque<int> &C, int cur){
	used[cur] = true;
	used2[cur] = true;
	
	C.push_back(cur);
	
	for(int nex : G[cur]){
		if(used[nex]){
			if(used2[nex]) {
				while(C.front() != nex){
					C.pop_front();
				}
				return true;
			} else {
				continue;
			}
		}
		
		if(cycle_detection(G, used, used2, C, nex)) return true;
	}
	
	C.pop_back();
	
	used2[cur] = false;
	
	return false;
}

deque<int> cycle_detection(const vector<vector<int>> &G){
	int N = G.size();
	vector<bool> used(N), used2(N);
	deque<int> C;
	
	for(int i = 0; i < N; i++){
		if(used[i] == true) continue;
		C.clear();
		if(cycle_detection(G, used, used2, C, i)) return C;
	}
	
	return {};
}

vector<vector<int>> Chu_Liu_Edmonds(vector<vector<pair<int,int>>> &G, int r, int &cost){
	int N = G.size();
	int tcost = 0;
	
	vector<vector<pair<int,int>>> R(N), NG;
	vector<vector<int>> T(N), NT;
	deque<int> C;
	vector<bool> c(N);
	vector<int> num(N), rnum(N);

	
	int nc;
	
	for(int i = 0; i < G.size(); i++){
		for(int j = 0; j < G[i].size(); j++){
			R[G[i][j].first].push_back({G[i][j].second, i});
		}
	}
	
	
	for(int i = 0; i < N; i++){
		sort(R[i].begin(), R[i].end());
		
		if(i == r) continue;
		
		if(R[i].size() == 0) {
			return {};
		}
		
		tcost += R[i][0].first;
		T[R[i][0].second].push_back(i);
	}
	
	
	C = cycle_detection(T);
	
	if(C.size() == 0){
		cost = tcost;
		return T;
	}
	
	for(int i = 0; i < C.size(); i++){
		c[C[i]] = true;
	}
	
	for(int i = 0, n = 0; i < N; i++){
		if(c[i] == true) {
			rnum[i] = -1;
			continue;
		}
		num[n] = i;
		rnum[i] = n;
		n++;
		
	}
	
	nc = N - C.size();
	
	NG.resize(nc+1);
	
	for(int i = 0, n = 0; i < N; i++){
		if(c[i] == true) {
			for(int j = 0; j < G[i].size(); j++){
				if(c[G[i][j].first] == false) {
					NG[nc].push_back({rnum[G[i][j].first], G[i][j].second});
				}
			}
			
		} else {
			for(int j = 0; j < G[i].size(); j++){
				if(c[G[i][j].first] == true) {
					NG[rnum[i]].push_back({nc, G[i][j].second - R[G[i][j].first][0].first});
				} else {
					NG[rnum[i]].push_back({rnum[G[i][j].first], G[i][j].second});
				}
			}
		}
	}
	
	NT = Chu_Liu_Edmonds(NG, rnum[r], cost);
	
	if(NT.size() == 0) return {};
	
	T.clear();
	T.resize(N);
	
	pair<int,int> e = {0,INF};
	
	
	for(int i = 0; i + 1 < NT.size(); i++){
		for(int j = 0; j < NT[i].size(); j++) {
			if(NT[i][j] == nc) {
				int fuga = 0;
				
				for(int k = 0; k < G[num[i]].size(); k++) {
					if(c[G[num[i]][k].first] == false) continue;
					
					
					if(G[num[i]][k].second - R[G[num[i]][k].first][0].first < e.second) {
						e.first = G[num[i]][k].first;
						e.second = G[num[i]][k].second - R[G[num[i]][k].first][0].first;
						fuga = R[G[num[i]][k].first][0].first;
					}
				}
				T[num[i]].push_back(e.first);
				
				cost += fuga;
				
			} else {
				T[num[i]].push_back(num[NT[i][j]]);
			}
		}
	}
	
	for(int i = 0; i < NT[nc].size(); i++){
		for(int j = 0; j < R[num[NT[nc][i]]].size(); j++){
			if(c[R[num[NT[nc][i]]][j].second] == true) {
				T[R[num[NT[nc][i]]][j].second].push_back(num[NT[nc][i]]);
				break;
			}
		}
	}
	
	for(int i = 0; i < C.size(); i++){
		if(C[(i+1)%C.size()] == e.first) continue;
		T[C[i]].push_back(C[(i+1)%C.size()]);
		cost += R[C[(i+1)%C.size()]][0].first;
	}
	
	return T;
}

int main(){
	vector<vector<pair<int,int>>> G;
	vector<vector<int>> T;
	int V, E, r, cost = 0;
	
	cin>>V>>E>>r;
	
	G.resize(V);
	
	for(int i = 0; i < E; i++){
		int s, t, w;
		
		cin>>s>>t>>w;
		
		G[s].push_back({t, w});
	}
	
	
	T = Chu_Liu_Edmonds(G, r, cost);
	
	if(T.size() == 0) cout<<-1<<endl;
	else {
		cout<<cost<<endl;
	}
	
	return 0;
}

