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;
}