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<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))

#define INF 200000000

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

struct OwnEdge
{
	int s, t, c;
	OwnEdge(int s,int t,int c):s(s),t(t),c(c){}
	OwnEdge():s(-1),t(-1),c(-1){}
	bool operator<(const OwnEdge& e)const
	{
		return c < e.c;
	}
	bool operator>(const OwnEdge& e)const
	{
		return c > e.c;
	}
};

ll MCA(vector<OwnEdge>& edges, int V, int r)
{
	vector<pii> mins(V, pii(INF, -1));
	for (auto& e : edges)
	{
		mins[e.t] = min(mins[e.t], pii(e.c, e.s));
	}
	mins[r] = pii(-1, -1);

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

	vector<bool> checked(V, false);
	for (int i = 0; i < V; i++)
	{
		if (checked[i])
		{
			continue;
		}
		vector<int> chain;
		int cursor = i;
		while (cursor != -1 && !checked[cursor])
		{
			checked[cursor] = true;
			chain.push_back(cursor);
			cursor = mins[cursor].second;
		}
		if (cursor != -1)
		{
			bool inCycle = false;
			for (auto& n : chain)
			{
				group[n] = counter;
				if (n == cursor)
				{
					inCycle = true;
					isCycle[counter] = true;
				}
				if (!inCycle)counter++;
			}
			if (inCycle)counter++;
		}
		else
		{
			for (auto& n : chain)
			{
				group[n] = counter;
				counter++;
			}
		}
	}

	if (counter == V)
	{
		ll sum = 1;
		for (int i = 0; i < V;i++)
		{
			sum += mins[i].first;
		}
		return sum;
	}

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

	vector<OwnEdge> newEdge;
	for (auto& e : edges)
	{
		int to = e.t;
		int gfrom = group[e.s];
		int gto = group[e.t];

		if (gfrom == gto)
		{
			continue;
		}
		else if (isCycle[gto])
		{
			newEdge.push_back(OwnEdge(gfrom, gto, e.c - mins[to].first));
		}
		else
		{
			newEdge.push_back(OwnEdge(gfrom, gto, e.c));
		}
	}

	return res + MCA(newEdge, counter, group[r]);
}

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

	vector<OwnEdge> edges;

	int V, E,r;
	scanf("%d %d %d", &V, &E, &r);

	for (int i = 0; i < E; i++)
	{
		int s, t, d;
		scanf("%d %d %d", &s, &t, &d);

		edges.push_back(OwnEdge(s, t, d));
	}

	printf("%d\n", MCA(edges, V, r));

	return 0;
}
