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
/**
 *
 * Chu-Liu/Edmonds's Algorithm
 *
 */

#include <vector>
#include <set>
using namespace std;

using edge = pair<int,pair<int,int>>;

int INF = 1 << 30;

int Edmonds(const vector<edge>& G,int V,int r){
  vector<pair<int,int>> MIN(V,pair<int,int>(INF,-1));
  for(auto &e : G){
    MIN[e.second.second] = min(MIN[e.second.second] , pair<int,int>(e.first,e.second.first));
  }

  MIN[r] = {-1,-1};

  vector<int> group(V,0);
  vector<bool> isCycle(V,false);
  int count = 0;

  vector<bool> used(V,false);

  for(int i = 0;i < V;i++){
    if(used[i]) continue;
    vector<int> chain;
    int now = i;
    while(now != -1 && !used[now]){
      used[now] = true;
      chain.push_back(now);
      now = MIN[now].second;
    }
    if(now != -1){
      bool inCycle = false;
      for(int j : chain){
        group[j] = count;
        if(j == now){
          isCycle[count] = true;
          inCycle = true;
        }
        if(!inCycle) 
          count++;
      }
      if(inCycle) 
        count++;
    }
    else{
      for(int j : chain){
        group[j] = count;
        count++;
      }
    }
  }
  int res = 0;
  if(count == V){
    for(int i = 0;i < V;i++){
      if(i == r) continue;
      res += MIN[i].first;
    }
    return res;
  }

  for(int i = 0;i < V;i++){
    if(i == r) continue;
    if(isCycle[group[i]])
      res += MIN[i].first;
  }

  vector<edge> nG;
  for(auto & e : G){
    int to = e.second.second;
    int gfrom = group[e.second.first];
    int gto = group[e.second.second];
    if(gfrom == gto) continue;
    else if(isCycle[gto])
      nG.push_back({e.first - MIN[to].first,{gfrom,gto}});
    else{
      nG.push_back({e.first,{gfrom,gto}});
    }
  }
  return res + Edmonds(nG,count,group[r]);
}

#include <iostream>

int main(){
  int V,E,r;
  cin >> V >> E >> r;
  vector<edge> G;

  for(int i = 0;i < E;i++){
    int s,t,w;
    cin >> s >> t >> w;
    G.push_back({w,{s,t}});
  }
  auto res = Edmonds(G,V,r);
  cout << res << endl;
}

