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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <stack>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
struct unionfind{
    vector<int> par, rk;
    unionfind() {}
    unionfind(int n):par(n), rk(n, 0){
        for(int i=0; i<n; i++) par[i]=i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    bool unite(int x, int y){
        x=find(x); y=find(y);
        if(x==y) return false;
        if(rk[x]>rk[y]) swap(x, y);
        par[x]=y;
        if(rk[x]==rk[y]) rk[y]++;
		return true;
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
};
template<typename T, typename E=T, bool ismin=true>
struct SkewHeap{
	using G=function<T(T, E)>;
	using H=function<E(E, E)>;
	struct Node{
		T key;
		E lazy;
		Node *l, *r;
	};

	const G g;
	const H h;
	SkewHeap(const G &g, const H &h):g(g), h(h){}

	Node *propagate(Node *t){
		if(t->lazy!=0){
			if(t->l) t->l->lazy=h(t->l->lazy, t->lazy);
			if(t->r) t->r->lazy=h(t->r->lazy, t->lazy);
			t->key=g(t->key, t->lazy);
			t->lazy=0;
		}
		return t;
	}

	Node *merge(Node *x, Node *y){
		if(!x) return y;
		if(!y) return x;
		propagate(x);
		propagate(y);
		if((x->key < y->key)^ismin) swap(x, y);
		x->r=merge(x->r, y);
		swap(x->l, x->r);
		return x;
	}

	void push(Node *&root, const T &key){
		root=merge(root, new Node({key, 0, nullptr, nullptr}));
	}

	T top(Node *&root){
		return propagate(root)->key;
	}

	T pop(Node *&root){
		T top=propagate(root)->key;
		auto *temp=root;
		root=merge(root->l, root->r);
		delete temp;
		return top;
	}

	bool empty(Node *root) const{
		return !root;
	}

	void add(Node *root, const E &lazy){
		if(root){
			root->lazy=h(root->lazy, lazy);
			propagate(root);
		}
	}

	Node *makeheap(){
		return nullptr;
	}
};
struct edge{
	int from, to;
	int cost;
	edge(){}
	edge(int from, int to, int cost):from(from), to(to), cost(cost){}
	bool operator<(const edge &e) const{ return cost<e.cost;};
};
int n, m;
vector<edge> edges;
ll DirectedMST(int r){
	ll ret=0;
	vector<int> used(n);
	unionfind uf(n);
	used[r]=2;
	using Heap=SkewHeap<edge, int>;
	using Node=Heap::Node;
	auto g=[](edge a, int b){ return edge(a.from, a.to, a.cost+b);};
	auto h=[](int a, int b){ return a+b;};
	Heap heap(g, h);
	vector<Node*> heaps(n, heap.makeheap());
	for(auto e:edges){
		heap.push(heaps[e.to], e);
	}
	for(int i=0; i<n; i++){
		if(used[i]!=0) continue;
		int cur=i;
		stack<int> processing;
		while(used[cur]!=2){
			processing.push(cur);
			used[cur]=1;
			if(heap.empty(heaps[cur])) return -1;
			auto e=heap.top(heaps[cur]);
			heap.add(heaps[cur], -e.cost);
			heap.pop(heaps[cur]);
			ret+=e.cost;
			int v=e.from;
			if(used[uf.find(v)]==1){
				int w;
				Node *merged=heap.makeheap();
				do{
					w=processing.top();
					processing.pop();
					used[w]=2;
					merged=heap.merge(merged, heaps[w]);
				}while(uf.unite(v, w));
				heaps[uf.find(v)]=merged;
				used[uf.find(v)]=1;
			}
			cur=uf.find(v);
		}
		while(!processing.empty()){
			used[processing.top()]=2;
			processing.pop();
		}
	}
	return ret;
}
int main()
{
	int r;
	cin>>n>>m>>r;
	for(int i=0; i<m; i++){
		int a, b, w;
		cin>>a>>b>>w;
		edges.push_back({a, b, w});
	}
	cout<<DirectedMST(r)<<endl;
    return 0;
}
