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 <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

void dfs(int v, const vector<vector<int> > &G, vector<bool> &used, vector<int> &vs) {
	used[v] = true;
	for(const auto &to : G[v]) {
		if(!used[to]) dfs(to, G, used, vs);
	}
	vs.push_back(v);
}

void rdfs(int v, int k, const vector<vector<int> > &rG, vector<bool> &used, vector<int> &cmp) {
	used[v] = true;
	cmp[v] = k;
	for(const auto &to : rG[v]) {
		if(!used[to]) rdfs(to, k, rG, used, cmp);
	}
}

int scc(const vector<vector<int> > &G, vector<int> &cmp) {
	const int n = G.size();
	vector<bool> used(n, false);
	vector<int> vs;
	vs.reserve(n);

	for(int v = 0; v < n; ++v) {
		if(!used[v]) dfs(v, G, used, vs);
	}

	vector<vector<int> > rG(n);
	for(int v = 0; v < n; ++v) {
		for(const auto &to : G[v]) {
			rG[to].emplace_back(v);
		}
	}

	fill(used.begin(), used.end(), false);
	int k = 0;
	for(int i = n - 1; i >= 0; --i) {
		if(!used[vs[i]]) rdfs(vs[i], k++, rG, used, cmp);
	}
	return k;
}

typedef int weight;
constexpr weight INF = (1 << 28);
constexpr weight EPS = 1e-8;

struct edge {
	int to;
	weight cost;
	edge(int to_, weight cost_):to(to_), cost(cost_){}
};

weight minimum_spanning_arborescence(int r, const vector<vector<edge> > &G, weight sum = 0) {
	const int n = G.size();

	vector<int> rev(n, -1);
	vector<weight> minimum_weight(n, INF);
	for(int v = 0; v < n; ++v) {
		for(const auto &e : G[v]) {
			if(minimum_weight[e.to] > e.cost + EPS) {
				minimum_weight[e.to] = e.cost;
				rev[e.to] = v;
			}
		}
	}

	vector<vector<int> > tG(n);
	for(int v = 0; v < n; ++v) {
		if(v == r) continue;
		if(rev[v] == -1) return INF;
		tG[rev[v]].emplace_back(v);
		sum += minimum_weight[v];
	}

	vector<int> cmp(n);
	const int num = scc(tG, cmp);
	if(num == n) return sum;

	vector<vector<edge> > next_G(num);
	for(int v = 0; v < n; ++v) {
		const int from = cmp[v];
		for(const auto &e : G[v]) {
			const int to = cmp[e.to];
			if(from == to) continue;

			const int cost = e.cost - minimum_weight[e.to];
			next_G[from].push_back({to, cost});
		}
	}

	return minimum_spanning_arborescence(cmp[r], next_G, sum);
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n, m, r;
	cin >> n >> m >> r;

	vector<vector<edge>> G(n);
	for(int i = 0; i < m; ++i) {
		int from, to, w;
		cin >> from >> to >> w;
		G[from].emplace_back(to, w);
	}

	cout << minimum_spanning_arborescence(r, G) << endl;

	return EXIT_SUCCESS;
}