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 <algorithm>
#include <limits>

using namespace std;

typedef pair<int, pair<int, int> > Edge;
typedef long long ll;

const int INF = numeric_limits<int>::max();

ll Chu_Liu_Edmonds(vector<Edge> edge, int V, int start){
	vector<pair<int, int> > mincost(V, make_pair(INF, -1));

	for (int i = 0; i < edge.size(); ++i)
	{
		Edge e = edge[i];
		mincost[e.second.second] = min(mincost[e.second.second], make_pair(e.first, e.second.first));
	}
	mincost[start] = make_pair(-1, -1);

	vector<int> group(V, 0);
	vector<bool> isCycle(V, false);
	int cnt = 0;

	vector<bool> used(V, false);
	for (int i = 0; i < V; ++i)
	{
		if (used[i]) continue;
		vector<int> chain;
		int cursor = i;
		while (cursor != -1 && !used[cursor]) {
			used[cursor] = true;
			chain.push_back(cursor);
			cursor = mincost[cursor].second;
		}
		if (cursor != -1) {
			bool inCycle = false;
			for (int j = 0; j < chain.size(); ++j) {
				group[chain[j]] = cnt;
				if (chain[j] == cursor) {
					isCycle[cnt] = true;
					inCycle = true;
				}
				if (!inCycle) cnt++;
			}
			if (inCycle) cnt++;
		}
		else {
			for (int j = 0; j < chain.size(); ++j) {
				group[chain[j]] = cnt;
				cnt++;
			}
		}
	}

	if (cnt == V)
	{
		ll ans = 1;
		for (int i = 0; i < V; ++i)
		{
			ans += mincost[i].first;
		}
		return ans;
	}

	ll res = 0;
	for (int i = 0; i < V; ++i) {
		if (i != start && isCycle[group[i]]) res += mincost[i].first;
	}

	vector<Edge> newEdge;
	for (int i = 0; i < edge.size(); ++i) {
		Edge e = edge[i];
		int to = e.second.second;
		int gfrom = group[e.second.first];
		int gto = group[e.second.second];
		if (gfrom == gto) continue;
		else if (isCycle[gto]) newEdge.push_back(make_pair(e.first - mincost[to].first, make_pair(gfrom, gto)));
		else newEdge.push_back(make_pair(e.first, make_pair(gfrom, gto)));
	}

	return res + Chu_Liu_Edmonds(newEdge, cnt, group[start]);
}


int main(int argc, char const *argv[])
{
	int V, E, r;
	cin >> V >> E >> r;
	vector<Edge> graph;
	for (int i = 0; i < E; ++i)
	{
		int s, t, w;
		cin >> s >> t >> w;
		graph.push_back(make_pair(w, make_pair(s,t)));
	}

	cout << Chu_Liu_Edmonds(graph, V, r) << endl;
	return 0;
}
