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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 10005

enum Type{
	NONE,
	START,
	FINISH,
};

struct Heap{
	Heap(){
		left = NULL;
		right = NULL;
		diff = 0;
		cost = 0;
		edge_id = 0;
	}

	Heap(int arg_cost,int arg_edge_id){
		left = NULL;
		right = NULL;
		diff = 0;
		cost = arg_cost;
		edge_id = arg_edge_id;
	}
	Heap *left,*right;
	int diff,cost,edge_id;
};

struct Edge{
	Edge(int arg_from,int arg_to,int arg_cost){
		from = arg_from;
		to = arg_to;
		cost = arg_cost;
	}
	int from,to,cost;
};

int V,E;
int boss[NUM];
int table_index;
int from_cost[NUM],FROM[NUM];
vector<Edge> edge;
Heap heap_table[1000005];
Heap* HEAP[NUM];
Type type[NUM];


void lazy(Heap* A){

	if(A->left){
		A->left->diff += A->diff;
	}
	if(A->right){
		A->right->diff += A->diff;
	}
	A->cost += A->diff;
	A->diff = 0;
}


Heap* meld(Heap* A,Heap* B){

	if(!A){
		return B;
	}
	if(!B){
		return A;
	}

	if((A->cost+A->diff) > (B->cost+B->diff)){
		swap(A,B);
	}

	lazy(A);

	A->right = meld(A->right,B);
	swap(A->left,A->right);

	return A;
}

Heap* pop(Heap *A){
	lazy(A);
	return meld(A->left,A->right);
}



int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	boss[boss_x] = boss_y;
}

void init(){

	for(int i = 0; i < V; i++){
		boss[i] = i;
	}
}

int MCA(int root){

	init();
	table_index = 0;

	for(int i = 0; i < V; i++){
		type[i] = NONE;
		HEAP[i] = NULL;
	}
	type[root] = FINISH;

	for(int i = 0; i < edge.size(); i++){

		heap_table[table_index] = Heap(edge[i].cost,i);
		HEAP[edge[i].to] = meld(HEAP[edge[i].to],&heap_table[table_index++]);
	}

	int ret = 0;

	for(int start = 0; start < V; start++){

		if(type[start] != NONE)continue;

		int current = start;
		vector<int> USED;

		while(type[current] != FINISH){

			type[current] = START;
			USED.push_back(current);

			if(!HEAP[current]){
				return BIG_NUM;
			}

			FROM[current] = get_boss(edge[HEAP[current]->edge_id].from);

			from_cost[current] = HEAP[current]->cost+HEAP[current]->diff;

			HEAP[current] = pop(HEAP[current]);

			if(FROM[current] == current)continue;

			ret += from_cost[current];

			if(type[FROM[current]] == START){

				int tmp = current;
				int debug = 0;

				do{
					if(HEAP[tmp]){
						HEAP[tmp]->diff -= from_cost[tmp];
					}

					if(tmp != current){
						unite(tmp,current);
						HEAP[current] = meld(HEAP[current],HEAP[tmp]);
					}

					tmp = get_boss(FROM[tmp]);

				}while(tmp != current);


			}else{
				current = FROM[current];
			}
		}

		for(int k = 0; k < USED.size(); k++){
			type[USED[k]] = FINISH;
		}
	}
	return ret;
}

int main(){

	int root;

	scanf("%d %d %d",&V,&E,&root);

	int from,to,cost;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d %d",&from,&to,&cost);

		edge.push_back(Edge(from,to,cost));
	}

	vector<int> ANS;
	int min_cost = BIG_NUM,tmp;

	printf("%d\n",MCA(root));

	return 0;
}


