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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

typedef long long int Weight;

const Weight INF = 2147483647;
const Weight ZERO = 0;
struct Edge {
	int src, dst;
	Weight weight;
	int id;
	Edge(int src_, int dst_, Weight weight_, const int id_) :
		src(src_), dst(dst_), weight(weight_), id(id_) { }
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
	Edge() :src(0), dst(0), weight(0) {

	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
namespace getcycle {
	vector<Edge>get_cycle(const Graph&g, const int start) {
		vector<Edge>prev_es(g.size());
		for (auto es : g) {
			for (auto e : es) {
				prev_es[e.dst] = e;
			}
		}
		for (int i = 0; i < int(g.size()); ++i) {
			if (i == start)continue;
			int now = i;
			vector<Edge>cycles;
			vector<int>comes(g.size(), -1);
			comes[now] = 0;
			int num = 1;
			while (1) {
				cycles.emplace_back(prev_es[now]);
				now = prev_es[now].src;
				if (comes[now] != -1) {
					cycles = vector < Edge>(cycles.begin() + comes[now], cycles.end());
					reverse(cycles.begin(), cycles.end());
					return cycles;
				}
				else if (now == start) {
					break;
				}
				comes[now] = num++;
			}
		}
		return vector<Edge>(0);
	}
}

//aoj2309???varify??????????????£??????????????§????????????????????????
pair<Weight, Graph> chu_liu(const Graph&g, const int start, const int e_size) {

	vector<Edge>cycle_edges;
	Weight total_len = 0;
	{
		Graph tree(g.size());
		{
			Graph revg(g.size());


			for (auto es : g) {
				for (auto e : es) {
					revg[e.dst].emplace_back(e.dst, e.src, e.weight,e.id);
				}
			}
			for (int node = 0; node < int(g.size()); ++node) {
				if (node == start)continue;
				else {
					Weight amin = INF;
					Edge min_edge;
					for (auto reve : revg[node]) {
						if (amin > reve.weight) {
							amin = reve.weight;
							min_edge = Edge(reve.dst, reve.src, reve.weight,reve.id);
						}
					}
					if (amin < INF) {
						total_len += min_edge.weight;
						tree[min_edge.src].emplace_back(min_edge);
					}
				}
			}
		}
		cycle_edges = getcycle::get_cycle(tree, start);
		if (cycle_edges.empty()) {
			return make_pair(total_len, tree);
		}
	}
	vector<bool>node_is_cycle(g.size());

	/*????´???°???Edge?????°????????§??????*/
	vector<int>edge_is_cycle(e_size);

	vector<Weight>prev_lens(g.size(), ZERO);

	for (auto ce : cycle_edges) {
		node_is_cycle[ce.src] = true;
		prev_lens[ce.dst] = ce.weight;
	}
	Graph newg(g.size());
	const int compress = cycle_edges[0].src;
	/*????´???°???Edge?????°????????§??????*/
	vector<Edge>memo(e_size);
	for (int s = 0; s < int(g.size()); ++s) {
		bool src_is_cycle = node_is_cycle[s];
		for (auto e : g[s]) {
			memo[e.id] = e;
			bool dst_is_cycle = node_is_cycle[e.dst];
			if (src_is_cycle&&dst_is_cycle) {
				continue;
			}
			else if (src_is_cycle) {
				e.src = compress;
			}
			else if (dst_is_cycle) {
				e.weight -= prev_lens[e.dst];
				e.dst = compress;
			}
			newg[e.src].push_back(e);
		}
	}
	auto p = chu_liu(newg, start, e_size);
	Graph compress_tree(p.second);
	Graph ans_tree(g.size());
	for (auto es : compress_tree) {
		for (auto e : es) {
			const Edge prev_edge(memo[e.id]);
			if (node_is_cycle[prev_edge.dst]) {
				for (auto cycle_edge : cycle_edges) {
					if (cycle_edge.dst != prev_edge.dst) {
						ans_tree[cycle_edge.src].emplace_back(cycle_edge);
					}
				}
			}
			ans_tree[prev_edge.src].emplace_back(prev_edge);
		}
	}
	Weight cycle_len = 0;
	for (auto e : cycle_edges) {
		cycle_len += e.weight;
	}
	return make_pair(p.first + cycle_len, ans_tree);
	
}

int main() {
	int V, E, R; cin >> V >> E >> R;
	Graph g(V);
	for (int i = 0; i < E; ++i) {
		int s, t, w; cin >> s >> t >> w;
		g[s].push_back(Edge(s, t, w,i));
	}
	auto p = chu_liu(g, R, E);
	cout << p.first << endl;
	return 0;
}