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 <vector>
#include <limits>
#include <iostream>
#include <cassert>
using namespace std;

template <typename T> class MinimumArborescence {
  typedef pair<int, T> Edge;
  typedef vector<vector<Edge> > Graph;
  static constexpr T INF = numeric_limits<T>::max();
  
public:
  MinimumArborescence() {}
  ~MinimumArborescence() {}

  int dfsCount(int v, vector<int> &visit, const Graph &G){
    int res  = 1;
    visit[v] = 1;
    for (const Edge &e : G[v]){
      if (visit[e.first] == -1) res += dfsCount(e.first, visit, G);
    }
    return res;
  }

  T solve(int r, Graph G){
    int n = G.size();
    
    // Check the existence of an arborescence
    vector<int> visit(n, -1);
    if (dfsCount(r, visit, G) != n) return INF;
    
    // Construct a reversed graph
    Graph H(n);
    for (int v = 0; v < n; v++){
      for (const Edge &e: G[v]){
        H[e.first].push_back(make_pair(v, e.second));
      }
    }
    
    T cost = 0;
    for (vector<int> active(n, true); ;){
      // cout << n << endl;
      vector<T>   min_cost(n, INF);
      vector<int> min_prev(n);
      vector<int> visit(n, -1);
      
      for (int v = 0; v < n; v++){
        for (const Edge &e : H[v]){
          if (v != r && active[v] && active[e.first] && e.second < min_cost[v]){
            min_cost[v] = e.second;
            min_prev[v] = e.first;
          }
        }
        // if (active[v] )  cout <<v << " " <<  min_cost[v] << " "<< min_prev[v] << endl;
      }
      
      bool has_cycle = false;
      for (int v = 0; v < n; v++){
        // cout << active[v] << " ";
      }
      // cout << endl;
      for (int u = 0; u < n; u++){
        if (visit[u] != -1 || !active[u] || u == r) continue;
        
        int v = visit[u] = u;
        // cout << u << endl;
        for (v = min_prev[v]; v != r && visit[v] == -1; v = min_prev[v]){
          // cout << v << " " << min_prev[v] << " " << visit[min_prev[v]] << endl;
          visit[v] = u;
        }
        
        
        if (visit[v] == u){     // cycle found
          vector<int> cycle_nodes;
          for (int w = v; cycle_nodes.empty() || w != v; w = min_prev[w]){
            active[w] = false;
            cycle_nodes.push_back(w);
          }
          active.push_back(true);
          H.push_back(vector<Edge>());
          G.push_back(vector<Edge>());
          for (int v : cycle_nodes){
            cost += min_cost[v];
            for (const auto &e : H[v]){
              if (active[e.first]){
                H[n].push_back(Edge(e.first, e.second - min_cost[v]));
                G[e.first].push_back(Edge(n, e.second - min_cost[v]));
                // cout << n << " " << v << " " << e.first << " " << e.second - min_cost[v] << endl;
                assert(e.second - min_cost[v] >= 0);
              }
            }
            for (const auto &e : G[v]){
              if (active[e.first]){
                G[n].push_back(Edge(e.first, e.second));
                H[e.first].push_back(Edge(n, e.second));
              } 
            }
          }
          has_cycle = true;
          n++;
        }
      }
      // cout << cost << endl;
      if (!has_cycle){
        for (int v = 0; v < n; v++){
          if (v != r && active[v]) cost += min_cost[v];
        }
        return cost;
      }
    }
  } 
};


int main(int argc, char *argv[])
{
  int n, m, r;
  cin >> n >> m >> r;
  vector<vector<pair<int, int> > > G(n);
  
  int s, t, w;
  for (int i = 0; i < m; i++){
    cin >> s >> t >> w;
    G[s].push_back(make_pair(t, w));
  }
  MinimumArborescence<int> solver;
  cout << solver.solve(r, G) << endl;
  return 0;
}