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 MXN 100010
// Pairing Heap with push, pop, erase, top (minimum), merge & decrease key
template<class T> struct PairingNode
{
	typedef struct PairingNode<T>* pnode;
	T val; // Value of the node
	pnode child, left, right; // Point to leftmost child, left sibling and right sibling
	// If a node is the leftmost child, left points to the parent.
};
template<class T> PairingNode<T>* _pairingnewnode(T val)
{
	typedef struct PairingNode<T>* pnode;
	pnode _new = new PairingNode<T>(); // Other method of allocating memory
	_new->val = val;
	return _new;
}
template<class T> struct pairing
{
	typedef struct PairingNode<T>* pnode;
	pnode root = 0; // Pointer to root
	int sz = 0; // Number of elements in the heap
	// Auxiliary functions
	int size()
	{
		return sz;
	}
	bool empty()
	{
		return !sz;
	}
	T top() // Minimum value
	{
		return root->val;
	}
	void swap(pnode &a, pnode &b) // Swaps two pnodes. Created to remove any reliance on STL
	{
		pnode c = a;
		a = b;
		b = c;
	}

	// Main functions
	pnode merge(pnode a, pnode b) // Merges two heaps into one heap
	{
		if (!b) return a;
		if (!a) return b;
		if (b->val < a->val) swap(a, b); // Make the heap with the smallest root the new root
		b->right = a->child;
		if (b->right) b->right->left = b;
		a->child = b;
		b->left = a;
		return a;
	}
	void merge(pairing *a) // Merges a heap into this heap
	{
		sz += a->sz;
		root = merge(root, a->root);
	}
	void push(pnode _new) // Inserts a pnode into the heap
	{
		sz++;
		if (sz == 1) // Just make this node the heap
		{
			root = _new;
			return;
		}
		if (_new->val < root->val) // Make _new the new root
		{
			_new->child = root;
			root->left = _new;
			root = _new;
		}
		else // Make _new the leftmost child of the root
		{
			_new->right = root->child;
			if (_new->right) _new->right->left = _new;
			root->child = _new;
			_new->left = root;
		}
	}
	pnode push(T val) // Inserts an element into the heap
	{
		pnode _new = _pairingnewnode<T>(val);
		push(_new);
		return _new;
	}
	pnode recursivemerge(pnode a) // Helps with the pop function. First merges pairs of trees, then merges the pairs into one tree
	{
		if (!a) return a;
		pnode b = a->right;
		if (!b) return a;
		pnode c = b->right;
		return merge(merge(a, b), recursivemerge(c));
	}
	void pop() // Removes the largest element from the heap
	{
		sz--;
		root = recursivemerge(root->child);
		if (root) root->right = nullptr;
	}
	void decreasekey(pnode a, T val)
	{
		a->val = val;
		if (a == root) return;
		if (a->left->child == a) // A is the leftmost child
		{
			a->left->child = a->right;
			if (a->right) a->right->left = a->left;
			a->left = a->right = nullptr;
			root = merge(root, a);
		}
		else
		{
			a->left->right = a->right;
			if (a->right) a->right->left = a->left;
			a->left = a->right = nullptr;
			root = merge(root, a);
		}
	}
};

// Union find with the ability to add x to a set
struct UF
{
	int rep[2*MXN], val[2*MXN], valatroot[2*MXN];
	void init()
	{
		for (int i = 0; i < 2*MXN; i++) rep[i] = i, val[i] = valatroot[i] = 0;
	}
	int findrep(int a)
	{
		if (rep[a] == a) return a;
		int b = rep[a];
		rep[a] = findrep(b);
		val[a] += valatroot[a] + val[b];
		valatroot[a] = 0;
		return rep[a] = rep[b]; 
	}
	bool connected(int a, int b)
	{
		return findrep(a) == findrep(b);
	}
	void merge(int a, int b) // Merge a into b
	{
		rep[findrep(a)] = findrep(b);
	}
	void addval(int a, int val) // Adds val to the a's component
	{
		valatroot[findrep(a)] += val;
	}
	int findval(int a)
	{
		int b = findrep(a);
		return val[a] + valatroot[b];
	}
};
UF scc, wcc; // Strongly and weakly connected components
// Represents an edge from u to v
struct Edge 
{
	int u, v, weight;
	Edge(int U, int V, int WEIGHT)
	{
		u = U, v = V, weight = WEIGHT;
	}
	Edge() {}
	int val() const
	{
		return weight - scc.findval(v);
	}
	bool operator<(const Edge e) const
	{
		return val() < e.val();
	}
};
pairing<Edge>* incoming[2*MXN]; // Represents incoming edges 
Edge par[2*MXN];
int minimalbranching(int n, int root, vector<pair<int, int> >* adj) // Finds the weight of the minimal branching rooted at node 0
{
	scc.init(), wcc.init();
	int ans = 0, upto = MXN;
	for (int i = 0; i < 2*MXN; i++) incoming[i] = new pairing<Edge>();
	// Push edges onto the pq
	for (int i = 0; i < n; i++)
	{
		for (auto b : adj[i])
		{
			incoming[b.first]->push(Edge(i, b.first, b.second));
		}
	}
	// Push all nodes other than the root onto a queue to be processed
	queue<int> q;
	for (int i = 0; i < n; i++) if (i != root) q.push(i);
	while (q.size())
	{
		int a = q.front();
		q.pop();
		if (scc.findrep(a) != a) continue;
		// Pop all edges off the incoming pq that come from within the scc
		while (1)
		{
			if (incoming[a]->empty()) return -1; // No branching exists
			if (scc.connected(incoming[a]->top().u, a)) incoming[a]->pop(); // In the same scc
			else break;
		}
		par[a] = incoming[a]->top();
		ans += par[a].val();
		incoming[a]->pop();
		if (!wcc.connected(par[a].u, par[a].v)) // Merge wcc's
		{
			wcc.merge(par[a].u, par[a].v);
		}
		else // A cycle has been formed, find the maximal edge on this cycle, remove and contract the cycle into one node
		{
			Edge mx = par[a];
			int b = scc.findrep(par[a].u);
			while (b != a)
			{
				mx = max(mx, par[b]);
				b = scc.findrep(par[b].u);
			}
			ans -= mx.val();
			int s = upto++; // New scc
			b = scc.findrep(par[a].u);
			while (b != s)
			{
				// Subtract weight of par[b] - mx from the weight of all edges going into b
				scc.addval(b, par[b].val() - mx.val());
				// Merge the pqs and sccs
				incoming[s]->merge(incoming[b]);
				scc.merge(b, s);
				b = scc.findrep(par[b].u);
			}
			// Process s later
			q.push(s);
		}
	}
	return ans;
}
vector<pair<int, int> > adj[MXN];
int main()
{
	int n, m, r;
	scanf("%d%d%d", &n, &m, &r);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		adj[a].emplace_back(b, c);
	}
	int ans = minimalbranching(n, r, adj);
	printf("%d\n", ans);
}
