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
// 参考:http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1060290#1

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

const int MAX = 105;
const int INF = 10001;

void visit(int V, int G[MAX][MAX], int v, int s, int r,
    vector<int> &no, vector< vector<int> > &comp,
    vector<int> &prev, vector< vector<int> > &next,
    vector<int> &mcost, vector<int> &mark,
    int &cost, bool &found) {
  if (mark[v]) {
    vector<int> temp = no;
    found = true;
    do {
      cost += mcost[v];
      v = prev[v];
      if (v != s) {
        while (comp[v].size() > 0) {
          no[comp[v].back()] = s;
          comp[s].push_back(comp[v].back());
          comp[v].pop_back();
        }
      }
    } while (v != s);
    
    //REP(i, V){
    for(int i = 0;i < V;++i){
      if(i != r && no[i] == s)
        //REP(j, V){
        for(int j = 0;j < V;++j){
          if (no[j] != s && G[j][i] < INF) G[j][i] -= mcost[temp[i]];
        }
    }
  }
  mark[v] = true;
  //REP(i, next[v].size())
  for(int i = 0;i < next[v].size();++i)
    if(no[next[v][i]] != no[v] && prev[no[next[v][i]]] == v)
      if (!mark[no[next[v][i]]] || next[v][i] == s)
        visit(V, G, next[v][i], s, r, no, comp, prev, next, mcost, mark, cost, found);

}

int minimumSpanningArborescence(int V, int E, int G[MAX][MAX], int r) {
  vector<int> no(V);
  vector< vector<int> > comp(V);
  for(int i = 0;i < V;++i) comp[i].push_back(no[i] = i);

  for(int cost = 0; ;) {
    vector<int> prev(V, -1);
    vector<int> mcost(V, INF);

    for(int i = 0;i < V;++i){
      for(int j = 0;j < V;++j){
        if(j == r || G[i][j] == INF || no[i] == no[j] || G[i][j] > mcost[no[j]]) continue;
        mcost[no[j]] = G[i][j];
        prev[no[j]] = no[i];
      }
    }
    vector< vector<int> > next(V);
    //REP(i, V)
    for(int i = 0;i < V;++i)
      if(prev[i] >= 0)
        next[prev[i]].push_back(i);

    bool stop = true;
    vector<int> mark(V, false);

    for(int i = 0;i < V;++i)
      if(i != r && !mark[i] && !comp[i].empty()) {
        bool found = false;
        visit(V, G, i, i, r, no, comp, prev, next, mcost, mark, cost, found);
        if (found) stop = false;
      }
    if (stop) {
      for(int i = 0;i < V;++i) if (prev[i] >= 0) cost += mcost[i];
      return cost;
    }
  }
}

int main() {
  int vNum,eNum,s;
  cin >> vNum >> eNum >> s;
  int G[MAX][MAX];
  for(int i = 0;i < vNum;++i)
    for(int j = 0;j < vNum;++j)
        G[i][j] = (i == j ? 0 : INF);

  for(int i = 0;i < eNum;++i){
    int v,e,w;
    cin >> v >> e >> w;
    G[v][e] = w;
  }
  cout <<minimumSpanningArborescence(vNum,eNum, G, s) <<endl;
}
