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;

struct edge
{
	int u, v, w;
	
	edge(void) {};
	edge(int a, int b, int c) :
		u(a), v(b), w(c) {};
		
	friend bool operator < (const edge &a, const edge &b)
	{
		return a.w < b.w;
	}
	
	friend bool operator > (const edge &a, const edge &b)
	{
		return a.w > b.w;
	}
};

class MCA
{
	private:
		
		const static int inf = 2e9;
		const static int maxn = 505;
		const static int maxm = 50005;
		
		edge inEdge[maxn];
		
		int vis[maxn], id[maxn];
	
	public:
		
		int MinCostArb(int n, int r, vector<edge> E)
		{
			int minCost = 0;
			
			while (true)
			{
				for (int i = 0; i < n; ++i)
					inEdge[i].w = inf;
					
				for (auto e : E)
					if (e.u != e.v
					&&  inEdge[e.v] > e)
						inEdge[e.v] = e;
						
				inEdge[r].w = 0;
				
				for (int i = 0; i < n; ++i)
					if (inEdge[i].w == inf)
						return inf;
						
				int cnt = 0;
				
				memset(id, -1, sizeof(id));
				memset(vis, -1, sizeof(vis));
				
				for (int i = 0; i < n; ++i)
				{
					minCost += inEdge[i].w;
					
					register int v = i;
					
					while (vis[v] != i && id[v] == -1 && v != r)
						vis[v] = i, v = inEdge[v].u;
						
					if (v != r && id[v] == -1)
					{
						register int u = inEdge[v].u;
						
						while (u != v)
							id[u] = cnt, u = inEdge[u].u;
							
						id[v] = cnt++;
					}
				}
				
				if (cnt == 0)break;
				
				for (int i = 0; i < n; ++i)
					if (id[i] == -1)id[i] = cnt++;
					
				for (auto &e : E)if (e.u != e.v)
				{
					e.w -= inEdge[e.v].w;
					e.u = id[e.u];
					e.v = id[e.v];
				}
				
				n = cnt, r = id[r];
			}
			
			return minCost;
		}
}mca;

signed main(void)
{
	int n, m, r;
		cin >> n >> m >> r;
		
	vector<edge> e;
		for (int i = 0; i < m; ++i)
		{
			int u, v, w;
				cin >> u >> v >> w;
			if (u != v)
				e.push_back(edge(u, v, w));
		}
		
	cout << mca.MinCostArb(n, r, e) << endl;
}