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

#define REP(i,s,n) for(int i=s;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX_V 200

using namespace std;
typedef long long ll;

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

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

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

struct Index{
  int from,to,edge;
  Index(int from=IINF,int to=IINF,int edge=IINF):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,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 = new Index[V];
  int *sub = new int[V];
  rep(i,V)y[i] = Index(IINF,IINF,IINF),sub[i] = IINF;
  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(IINF,IINF,IINF))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(IINF,IINF,IINF))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(IINF,IINF,IINF))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] == IINF || from == to)continue;
      G[i][j].cost -= sub[to];
    }
  }

  int *ngroup = new int[(int)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(IINF,IINF,IINF))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));
  }
  delete [] ngroup;
  delete [] y;
  delete [] sub;
}

void cdfs(const 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(const 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(){
  //int T,CNT = 1;
  //cin >> T;
  //while(T--){
      Error = false;
      int root = 0;
      scanf("%d %d",&N,&M);
      cin >> root;

      vve G(N);
      rep(i,M){
	int from,to,cost;
	scanf("%d %d %d",&from,&to,&cost);
	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;//cout << "Case #" << CNT++ << ": " << cost << endl;
      //else       cout << "Case #" << CNT++ << ": Possums!" << endl;
      //}
    
  return 0;
}