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<cassert>
#include<cstdio>
#include<queue>
#include<deque>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX_V 200

using namespace std;
typedef long long ll;

struct P
{
  int x,y;
  P(int x=inf,int y=inf):x(x),y(y){}
};

struct Pox
{
  int from,to;
  int cost;
  Pox(int from=inf,int to=inf,int cost=inf):from(from),to(to),cost(cost){}
};

struct edge
{
  int to;
  int cost;
  edge(int to=inf,int cost=inf):to(to),cost(cost){}
  bool operator < (const edge& a)const
  {
    return cost < a.cost;
  }
};

struct Index
{
  int from,to;
  int edge;
  Index(int from=inf,int to=inf,int edge=inf):from(from),to(to),edge(edge){}
  bool operator < (const Index &a)const
  {
    if(from != a.from)return from < a.from;
    if(to != a.to)return to < a.to;
    return edge < a.edge;
  }

  bool operator == (const Index &a)const
  {
    return (from == a.from && to == a.to && edge == a.edge);
  }
};

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<edge> ve;
typedef vector<ve>  vve;
int N,M;

//Strongly Connected Componet
class SCC
{
public:
  int SCC_V;
  vi SCC_G[MAX_V];
  vi SCC_rG[MAX_V];
  vi SCC_vs;
  bool SCC_used[MAX_V];
  int SCC_cmp[MAX_V];

  SCC(int V):SCC_V(V)
  {
    SCC_init(V);
  }

  void SCC_init(int NN)
  {
    SCC_V = NN;
    rep(i,NN)
      {
	SCC_G[i].clear();
	SCC_rG[i].clear();
      }
  }

  void add_edge(int from,int to)
  {
    SCC_G[from].push_back(to);
    SCC_rG[to].push_back(from);
  }

  void dfs(int v)
  {
    SCC_used[v] = true;
    for(int i=0;i<SCC_G[v].size();i++)
      if(!SCC_used[SCC_G[v][i]])dfs(SCC_G[v][i]);
    SCC_vs.push_back(v);
  }

  void rdfs(int v,int k)
  {
    SCC_used[v] = true;
    SCC_cmp[v] = k;
    for(int i=0;i<SCC_rG[v].size();i++)
      if(!SCC_used[SCC_rG[v][i]])rdfs(SCC_rG[v][i],k);
  }

  int scc()
  {
    for(int i=0;i<MAX_V;i++)SCC_used[i] = false;
    SCC_vs.clear();
    for(int v=0;v<SCC_V;v++)
      if(!SCC_used[v])dfs(v);
    for(int i=0;i<MAX_V;i++)SCC_used[i] = false;
    int k = 0;
    int cnt;

    for(int i=SCC_vs.size()-1;i>=0;i--)
      {
	cnt = 0;
	if(!SCC_used[SCC_vs[i]])rdfs(SCC_vs[i],k++);
      }
    return k;
  }
};
// --------------------------------------- SCC fin

/***
    V : ???????????則?????????????????属 (???????????則????????????????????卒????????????????????属????????????????????即????????卒?????????)
    root : ?????????
    G : ??属????????????????賊???則????????????????????????
    tree : ????属?????????即?????即
    goup : ??????????賊???????????????属?????????
    gused : ????????属??????????????????????????????????????????
    prev : ????????????????賊???則????????贈????????????????????賊
***/

bool Error;

void Minimum_Cost_Arborescence_Algorithm(int V,int root,vve G,vve &tree,bool *used,int *group,bool *gused,vector<Index> &prev)
{
  if(Error)return;
  /*
    y[i] := ??則??????????????属????????則????????????i??????????????????????????則????属??????????????????????????????則???????????????????????属????????則??????????????????????????????????????????????????????????????????
    sub[i] := ?????????i?????\??贈???????????????????属????????????則?????????????????????????????\?????即?????????????????????
  */

  Index y[V];
  int sub[V];
  rep(i,V)y[i] = Index(inf,inf,inf),sub[i] = inf;
  rep(i,G.size())
    {
      int from = group[i];	  
      rep(j,G[i].size())
	{
	  int to = group[G[i][j].to];
	  if(to == group[root])continue;//root?????\?????????????則???則?????????????????則?????????
	  if(from == to)continue;//???????????????????????則?????????
	  int cost = G[i][j].cost;
	  if(y[to] == Index(inf,inf,inf))y[to] = Index(i,G[i][j].to,j);
	  else if(G[y[to].from][y[to].edge].cost > cost)y[to] = Index(i,G[i][j].to,j);
	}
    }

  SCC scc(V);

  int ECNT = 0;
  rep(i,V)
    {
      if(y[i] == Index(inf,inf,inf))continue;//?????????i?????\??贈?????????????????????
      scc.add_edge(group[y[i].from],i);//?????????i????????????y[i].first???????????\???
      sub[i] = G[y[i].from][y[i].edge].cost;
      ECNT++;
    }

  if(ECNT != V-1)
    {
      Error = true;
      return;
    }

  int nV = scc.scc();

  if(V == nV)//???????????????
    {
      rep(i,V)
	{
	  if(y[i] == Index(inf,inf,inf))continue;
	  int from = y[i].from;
	  int to = y[i].to;
	  if(used[to])continue;
	  int e = y[i].edge;
	  used[to] = true;
	  prev.push_back(y[i]);
	  tree[from].push_back(edge(to,e));
	}
      return;
    }

  rep(i,G.size())
    {
      int from = group[i];
      rep(j,G[i].size())
	{	  
	  int to = group[G[i][j].to];
	  if(sub[to] == inf || from == to)continue;
	  G[i][j].cost -= sub[to];
	}
    }

  int ngroup[G.size()];
  rep(i,G.size())ngroup[i] = scc.SCC_cmp[group[i]];

  Minimum_Cost_Arborescence_Algorithm(nV,root,G,tree,used,&ngroup[0],&gused[0],prev);
  if(Error)return;
  rep(i,G.size())gused[i] = false;

  rep(i,prev.size())
    {
      int from = prev[i].from;
      int to = prev[i].to;
      gused[group[to]] = true;
      used[to] = true;
    }
  rep(i,V)
    {
      if(y[i] == Index(inf,inf,inf))continue;
      int from = y[i].from;
      int to = y[i].to;
      if(used[to])continue;
      if(gused[group[to]])continue;
      int e = y[i].edge;
      used[to] = true;
      gused[group[to]] = true;
      prev.push_back(y[i]);
      tree[from].push_back(edge(to,e));
    }


}

void cdfs(vve &G,int cur,bool *visited)
{

  if(visited[cur])return;

  visited[cur] = true;
  rep(i,G[cur].size())
    cdfs(G,G[cur][i].to,visited);

}


bool check(vve &G,int root)
{
  bool visited[G.size()];
  rep(i,G.size())visited[i] = false;
  cdfs(G,root,&visited[0]);
     
  rep(i,G.size())if(!visited[i])
    return false;
  return true;
}



int main()
{
  bool Error = false;
  int root;
  scanf("%d %d %d",&N,&M,&root);
  assert(1 <= N && N <= 100);
  assert(0 <= M && M <= 1000);
  assert(0 <= root && root < N);

  vve G(N);
  rep(i,M)
    {
      int from,to,cost;
      scanf("%d %d %d",&from,&to,&cost);
      assert(0 <= from && from < N);
      assert(0 <= to   && to   < N);
      assert(0 <= cost    && cost    <= 10000);
      if(!(0 <= from && from < N && 0 <= to && to < N))Error = true;
      if(Error)continue;
      G[from].push_back(edge(to,cost));
    }

  vve tree(N); //?????????????????????
  bool used[N];//??蔵?????即????????????????????????
  int group[N];  //????????属?????????????賊???????????????????
  bool group_used[N];
  vector<Index> pre; // ?????????????????????????????贈??????
  rep(i,N)used[i] = group_used[i] = false,group[i] = i;
  Error = false;

  if(!check(G,root))Error = true;

  if(!Error)
    Minimum_Cost_Arborescence_Algorithm(N,root,G,tree,&used[0],&group[0],&group_used[0],pre);

  int cost = 0;
  rep(i,N)
    {
      rep(j,tree[i].size())
	{
	  cost += G[i][tree[i][j].cost].cost;
	}
    }

  if(!Error)
    {
      cout << cost << endl;
    }
  else 
    {
      cout << "no answer" << endl;
      assert(false);
    }

  return 0;
}