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;

const int N = 100005;
const int E = 1000000;
const int inf = 2139062143;

struct edge {
	int u, v, len, id;
}e[N];
int chosen[E];
int pre[N], inwei[N], innum[N], id[N], vis[N];
int inc[E], decr[E], pos;

inline int mst(int n, int m, int root = 1) {
	memset(inc,0,sizeof(inc));
	memset(decr,0,sizeof(decr));
	memset(chosen,0,sizeof(chosen));
	int ans = 0, eg = m;
	pos = m;
	while (true) {
		memset(inwei, 127, sizeof(int) * (n + 2));
		memset(id, 0, sizeof(int) * (n + 2));
		memset(vis, 0, sizeof(int) * (n + 2));
		for (int i = 1; i <= m; i++)
			if (e[i].len < inwei[e[i].v]) {
				inwei[e[i].v] = e[i].len;
				pre[e[i].v] = e[i].u;
				innum[e[i].v] = e[i].id;
			}
		inwei[root] = 0;
		for (int i = 1; i <= n; i++)
			if (inwei[i] == inf) return -1;
		int tot = 0;
		for (int i = 1; i <= n; i++) {
			ans += inwei[i];
			if (i != root) chosen[innum[i]]++;
			int j = i;
			while (vis[j] != i && j != root && !id[j])
				vis[j] = i, j = pre[j];
			if (j != root && !id[j]) {
				id[j] = ++tot;
				for (int k = pre[j]; k != j; k = pre[k]) id[k] = tot;
			}
		}
		if (!tot) break;
		for (int i = 1; i <= n; i++)
			if (!id[i]) id[i] = ++tot;
		n = tot;
		for (int i = 1; i <= m; i++) {
			int v = e[i].v;
			e[i].v = id[e[i].v];
			e[i].u = id[e[i].u];
			if (e[i].v != e[i].u) {
				e[i].len -= inwei[v];
				pos++;
				inc[pos] = e[i].id;
				decr[pos] = innum[v];
				e[i].id = pos;
			}
			else swap(e[i--], e[m--]);
		}
		root = id[root];
	}
	while (pos > eg) {
		if (chosen[pos] > 0) {
			chosen[inc[pos]]++;
			chosen[decr[pos]]--;
		}
		pos--;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int casos = 1;
//	cin >> casos;
	for (int cas = 1; cas <= casos; ++cas) {
	//	cout << "Case #" << cas << ": ";
		int n, m, r;
		cin >> n >> m >> r;
		for (int i = 1; i <= m; ++i) {
			e[i].id = i;
			cin >> e[i].u >> e[i].v >> e[i].len;
			++e[i].u;
			++e[i].v;
		}
		int res = mst(n,m, r+1);
		if (res == -1) cout << "Possums!\n";
		else cout << res << '\n';
	}
}

