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
/*
 * Minimum-Cost Arborescence
 * Constraints
 * 1 ≤ |V| ≤ 100
 * 0 ≤ |E| ≤ 1,000
 * 0 ≤ wi ≤ 10,000
 * G has arborescence(s) with the root r
 */

#include <algorithm>
#include <iostream>
#include <set>
#include <stack>
#include <vector>

#define MAXN 110
#define MAXM 1010000
#define INF 11000

using namespace std;

struct edge {
  int from, to, wt, next;
} E[2 * MAXM];

struct dfsdata {
  int id, parent;
  bool after;
};

int LE[2 * MAXN];
bool active[2 * MAXN];

int next_m = MAXM;
int next_n = MAXN;
int n, m, r;

int CMCA(int nactive) {
  if (nactive == 1)
    return 0;
  int m[2 * MAXN];
  fill(m, m + 2 * MAXN, INF);
  for (int i = 0; i < 2 * MAXN; ++i) {
    if (!active[i])
      continue;
    for (int e = LE[i]; e != -1; e = E[e].next) {
      if (!active[E[e].to])
        continue;
      m[E[e].to] = min(m[E[e].to], E[e].wt);
    }
  }
  bool flag[2 * MAXN]{0};
  set<int> fstar;
  for (int i = 0; i < 2 * MAXN; ++i) {
    if (!active[i])
      continue;
    for (int e = LE[i]; e != -1; e = E[e].next) {
      if (!active[E[e].to])
        continue;
      E[e].wt -= m[E[e].to];
      if (E[e].wt == 0 && !flag[E[e].to] && E[e].to != r) {
        fstar.insert(e);
        flag[E[e].to] = true;
      }
    }
  }

  stack<dfsdata> dfs;
  bool visited[2 * MAXN]{0};
  int parent[2 * MAXN]{0}, pre[2 * MAXN]{0}, post[2 * MAXN]{0};
  int clk = 0;

  for (int i = 0; i < 2 * MAXN; ++i) {
    if (!visited[i] and active[i]) {
      dfs.push({i, -1, false});
      while (!dfs.empty()) {
        dfsdata d = dfs.top();
        dfs.pop();
        if (visited[d.id] && !d.after)
          continue;
        if (visited[d.id] && d.after) {
          post[d.id] = ++clk;
        }
        if (!visited[d.id]) {
          pre[d.id] = ++clk;
          visited[d.id] = true;
          parent[d.id] = d.parent;
          dfs.push({d.id, d.parent, true});
          for (int e = LE[d.id]; e != -1; e = E[e].next) {
            if (!fstar.count(e) or visited[E[e].to])
              continue;
            dfs.push({E[e].to, d.id, false});
          }
        }
      }
    }
  }

  for (int e : fstar) {
    if (pre[E[e].to] < pre[E[e].from] &&
        post[E[e].to] > post[E[e].from]) { // cycle
      bool in_cycle[2 * MAXN]{0};
      vector<int> C;
      int curr = E[e].from;
      while (curr != E[e].to) {
        C.push_back(curr);
        curr = parent[curr];
      }
      C.push_back(E[e].to); // post: C contains all nodes in the cycle
      for (int u : C)
        in_cycle[u] = true;

      int cv = next_n++;
      for (int i = 0; i < 2 * MAXN; ++i) {
        if (!active[i])
          continue;
        for (int ei = LE[i]; ei != -1; ei = E[ei].next) {
          if (!active[E[ei].to])
            continue;
          if (in_cycle[i] && !in_cycle[E[ei].to]) {
            E[next_m] = {cv, E[ei].to, E[ei].wt, LE[cv]};
            LE[cv] = next_m;
            if (LE[cv] > 2 * MAXM)
              cout << "!";
            ++next_m;
          }
          if (!in_cycle[i] && in_cycle[E[ei].to]) {
            E[next_m] = {i, cv, E[ei].wt, LE[i]};
            LE[i] = next_m;
            if (LE[i] > 2 * MAXM)
              cout << "!";
            ++next_m;
          }
        }
      }

      int c0 = 0;
      for (int i = 0; i < 2 * MAXN; ++i) {
        if (active[i] and i != r)
          c0 += m[i];
      }
      for (int v : C)
        active[v] = false;
      active[cv] = true;
      return c0 + CMCA(nactive - C.size() + 1);
    }
  }
  int to_return = 0;
  for (int i = 0; i < 2 * MAXN; ++i) {
    if (active[i] and i != r)
      to_return += m[i];
  }
  return to_return;
}

int main() {
  cin >> n >> m >> r;
  fill(LE, LE + 2 * MAXN, -1);
  fill(active, active + n, true);
  fill(active + n, active + 2 * n, false);
  for (int src, dst, cost, i = 0; i < m; ++i) {
    cin >> src >> dst >> cost;
    E[i] = {src, dst, cost, LE[src]};
    LE[src] = i;
  }
  cout << CMCA(n) << endl;
}
