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>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, char, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

const ll mod = 1000000007;

static const ll INF = 1e15;

struct minimum_spanning_arborescence_runner {
	typedef ll weight;
	typedef vector<vector<ll>> matrix;

	void backward_traverse(int v, int s, int r, matrix& g,
		vector<int>& no, vector< vector<int> >& comp,
		vector<int>& prev, vector<weight>& mcost,
		vector<int>& mark, weight& cost, bool& found) {
		const int n = g.size();
		if (mark[v]) {
			vector<int> temp = no;
			found = true;
			do {
				cost += mcost[v];
				v = prev[v];
				if (v != s) {
					while (comp[v].size() > 0) {
						no[comp[v].back()] = s;
						comp[s].push_back(comp[v].back());
						comp[v].pop_back();
					}
				}
			} while (v != s);
			for (int j = 0; j < n; ++j)
				if (j != r && no[j] == s)
					for (int i = 0; i < n; ++i)
						if (no[i] != s && g[i][j] < INF)
							g[i][j] -= mcost[temp[j]];
		}
		mark[v] = true;
		for (int i = 0; i < n; ++i)
			if (no[i] != no[v] && prev[no[i]] == v)
				if (!mark[no[i]] || i == s)
					backward_traverse(i, s, r, g,
						no, comp, prev, mcost, mark, cost, found);
	}

	weight minimum_spanning_arborescence(int r, matrix& g) {
		const int n = g.size();

		vector<int> no(n);
		vector< vector<int> > comp(n);
		for (int i = 0; i < n; ++i) {
			no[i] = i;
			comp[i].push_back(i);
		}
		weight cost = 0;
		while (1) {
			vector<int> prev(n, -1);
			vector<weight> mcost(n, INF);
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					if (j == r) continue;
					if (no[i] != no[j] && g[i][j] < INF) {
						if (g[i][j] < mcost[no[j]]) {
							mcost[no[j]] = g[i][j];
							prev[no[j]] = no[i];
						}
					}
				}
			}
			bool stop = true;
			vector<int> mark(n);
			for (int i = 0; i < n; ++i) {
				if (i == r || mark[i] || comp[i].size() == 0) continue;
				bool found = false;
				backward_traverse(i, i, r, g,
					no, comp, prev, mcost, mark, cost, found);
				if (found) stop = false;
			}
			if (stop) {
				for (int i = 0; i < n; ++i)
					if (prev[i] >= 0)
						cost += mcost[i];
				return cost;
			}
		}
	}

};


int main(void)
{
	int v, e, r;
	cin >> v >> e >> r;

	vector<vector<ll>> g(v,vector<ll>(v, INF));
	rep(i, e) {
		ll s, t, c;
		cin >> s >> t >> c;
		g[s][t] = c;
	}
	minimum_spanning_arborescence_runner runner;
	auto w = runner.minimum_spanning_arborescence(r, g);
	cout << w << endl;
	return 0;
}

