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
bool debug=false;
#include <stdio.h>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
#define PB push_back
#define F first
#define S second
const int N=6e3+10;
const int INF=1e9+10;
vector<pair<int,int>> graph[N];
int in[N],from[N],a[N],p[N],s[N],went[N];
int run(int root,int v){
	if(root+1==v)return 0;
	if(debug){
		printf("run(%d,%d)\n",root,v);
		for(int i=root;i<v;i++)for(pair<int,int> j:graph[i])printf("%d to %d cost=%d\n",i,j.F,j.S);
		printf("done debug\n");
	}
	int now,ans=0,tt,nv=v+1;
	for(int i=root;i<v;i++)from[i]=-1,in[i]=INF,went[i]=0;
	for(int i=root;i<v;i++)for(pair<int,int> j:graph[i])if(in[j.F]>j.S){
		from[j.F]=i;
		in[j.F]=j.S;
	}
	for(int i=root+1;i<v;i++)if(from[i]==-1)return -INF;
	else ans+=in[i];
	graph[v].clear();
	for(int i=root;i<v;i++)p[i]=v;
	went[root]=-2;
	for(int i=root+1;i<v;i++)if(went[i]==0){
		if(debug)printf("i=%d::\n",i);
		now=i;
		while(went[now]==0){
			if(debug)printf("dfs %d\n",now);
			went[now]=-1;
			now=from[now];
		}
		if(went[now]==-1){
			tt=now;
			now=i;
			while(now!=tt){
				went[now]=-4;
				now=from[now];
			}
			if(debug)printf("find ring\nnow=%d\n",now);
			p[now]=nv;
			graph[nv].clear();
			went[now]=-3;
			now=from[now];
			while(now!=tt){
				p[now]=nv;
				went[now]=-3;
				if(debug)printf("p[now=%d]=%d\n",now,p[now]);
				now=from[now];
			}
			nv++;
		}
		if(went[now]==-2){
			now=i;
			while(went[now]==-1){
				went[now]=-2;
				now=from[now];
			}
		}
		else {
			now=i;
			while(went[now]==-1){
				went[now]=-4;
				now=from[now];
			}
		}
	}
	for(int i=root;i<v;i++)if(went[i]!=-2&&p[i]==v)p[i]=nv++;
	if(debug)for(int i=root;i<v;i++)printf("p[%d]=%d\n",i,p[i]);
	if(debug)for(int i=root;i<v;i++)printf("went[%d]=%d\n",i,went[i]);
	for(int i=root;i<v;i++)for(pair<int,int> j:graph[i])if(p[j.F]!=p[i]&&went[j.F]!=-2)graph[p[i]].PB({p[j.F],j.S-in[j.F]});
	ans+=run(v,nv);
	return ans;
}
void solve(int n,int m,int root){
	int ans,l,r,x,y,c;
	for(int i=0;i<n;i++)graph[i].clear();
	while(m--){
	    scanf("%d%d%d",&l,&r,&c);
	    if(r==root)continue;
	    else if(l==root)graph[0].PB({r==0?root:r,c});
	    else graph[l==0?root:l].PB({r==0?root:r,c});
	}
	ans=run(0,n);
	if(ans<0)printf("-1\n");
	else printf("%d\n",ans);
}
int main(){
    int n,m,r;
    scanf("%d%d%d",&n,&m,&r);
	solve(n,m,r);
}

