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<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int MAX=100;

class edge
{
public:
	int src,tar,w;
	edge(int src=0,int tar=0,int w=0):src(src),tar(tar),w(w){}
};

int n;
vector<edge> G[MAX];

int cost;
vector<edge> GG[MAX];//reverse edge
int num[MAX],pre[MAX],mcost[MAX];//number, prev of vertex, edges min cost
bool mark[MAX];//vertex used flag
vector<int> comp[MAX];//compressed vertex
vector<int> nex[MAX];//next of vertex

void cycle(int v,int s,int r,bool &found)
{
	if(mark[v])
	{
		int temp[MAX];
		for(int i=0;i<n;i++)temp[i]=num[i];
		found=true;
		do
		{
			cost+=mcost[v];
			v=pre[v];
			if(v!=s)
			{
				while(!comp[v].empty())
				{
					num[comp[v].back()]=s;
					comp[s].push_back(comp[v].back());
					comp[v].pop_back();
				}
			}
		}while(v!=s);
		
		for(int i=0;i<comp[s].size();i++)
		{
			int j=comp[s][i];
			if(j!=r)
			{
				for(int k=0;k<GG[j].size();k++)
				{
					if(num[GG[j][k].src]!=s)
					{
						GG[j][k].w-=mcost[temp[j]];
					}
				}
			}
		}
	}
	
	mark[v]=true;
	for(int k=0;k<nex[v].size();k++)
	{
		int i=nex[v][k];
		if(num[i]!=num[v]&&pre[num[i]]==v)
		{
			if(!mark[num[i]]||i==s)
			{
				cycle(i,s,r,found);
			}
		}
	}
	return;
}

int mincosttree(int r)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<G[i].size();j++)
		{
			GG[G[i][j].tar].push_back(G[i][j]);
		}
	}
	
	for(int i=0;i<n;i++)
	{
		num[i]=i;
		comp[i].push_back(i);
	}
	cost=0;
	
	while(1)
	{
		for(int i=0;i<n;i++)
		{
			pre[i]=-1;
			mcost[i]=1<<28;
		}
		
		for(int j=0;j<n;j++)
		{
			if(j==r)continue;
			for(int k=0;k<GG[j].size();k++)
			{
				int i=GG[j][k].src;
				if(num[i]!=num[j])
				{
					if(GG[j][k].w<mcost[num[j]])
					{
						mcost[num[j]]=GG[j][k].w;
						pre[num[j]]=num[i];
					}
				}
			}
		}
		
		for(int i=0;i<n;i++)
		{
			if(pre[i]>=0)
			{
				nex[pre[i]].push_back(i);
			}
		}
		
		bool stop=true;
		for(int i=0;i<n;i++)mark[i]=false;
		
		for(int i=0;i<n;i++)
		{
			if(i==r||mark[i]||comp[i].empty())continue;
			bool found=false;
			cycle(i,i,r,found);
			if(found)stop=false;
		}
		if(stop)
		{
			for(int i=0;i<n;i++)
			{
				if(pre[i]>=0)
				{
					cost+=mcost[i];
				}
			}
			return cost;
		}
	}
}

int main()
{
	int e,r;cin>>n>>e>>r;
	int s,t,w;
	for(int i=0;i<e;i++)
	{
		cin>>s>>t>>w;
		G[s].push_back(edge(s,t,w));
	}
	cout<<mincosttree(r)<<endl;
	return 0;
}