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 <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <bitset>
#include <complex>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
#define pb push_back
#define mp make_pair
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
typedef unsigned long long ull;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const int INF = 1 << 27;
const int MAX_V = 101;
//////////////////////////////
// ????°?????????¨?????¨
void visit(int V, int G[MAX_V][MAX_V], 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){
      if(i != r && no[i] == s)
        REP(j, V){
          if (no[j] != s && G[j][i] < INF) G[j][i] -= mcost[temp[i]];
        }
    }
  }
  mark[v] = true;
  REP(i, next[v].size())
    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_V][MAX_V], int r) {
  vector<int> no(V);
  vector< vector<int> > comp(V);
  REP(i, V) comp[i].push_back(no[i] = i);

  for(int cost = 0; ;) {
    vector<int> prev(V, -1);
    vector<int> mcost(V, INF);
    REP(i, V){
      REP(j, V){
        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)
      if(prev[i] >= 0)
        next[prev[i]].push_back(i);
    bool stop = true;
    vector<int> mark(V, false);
    REP(i, V)
      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) {
      REP(i, V) if (prev[i] >= 0) cost += mcost[i];
      return cost;
    }
  }
}
int main() {
  int V, E, r;
  cin >>V >>E >>r;
  int G[MAX_V][MAX_V];
  REP(i, V) REP(j, V) G[i][j] = (i == j ? 0 : INF);
  REP(i, E){
    int f, t, c; cin >>f >>t >>c;
    G[f][t] = c;
  }
  cout <<minimumSpanningArborescence(V, E, G, r) <<endl;
  return 0;
}