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 <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;

#define INF 1001001001

struct Edge {
  int from;
  int to;
  int cost;
  Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
};

using Graph = vector< vector<Edge> >;

int dfs(Graph G, int r) {
  int n = G.size();
  vector<int> minEdge(n,-1);
  vector<int> minCost(n,INF);

  // T*構成
  for (auto es : G) {
    for (auto e : es) {
      if (e.to == r) continue;
      if (e.cost < minCost[e.to]) {
        minEdge[e.to] = e.from;
        minCost[e.to] = e.cost;
      }
    }
  }

  // 閉路検出
  int v = -1;
  rep(i,n) {
    if (minEdge[i]==-1) continue;
    vector<bool> isVisited(n);
    int now = i;
    while (now != r && !isVisited[now]) {
      isVisited[now] = true;
      now = minEdge[now];
    }
    if (now != r) {
      v = now;
      break;
    }
  }

  // 閉路なしの場合
  if (v == -1) {
    int ans = 0;
    rep(i,n) {
      if (minEdge[i]==-1) continue;
      ans += minCost[i];
    }
    return ans;
  }

  // 閉路ありの場合
  int ans = 0;
  int now = v;
  vector<bool> onCycle(n);
  while (!onCycle[now]) {
    onCycle[now] = true;
    ans += minCost[now];
    now = minEdge[now];
  }

  // グラフを縮約
  Graph newG(n);
  rep(i,n) {
    for (auto e : G[i]) {
      int s = e.from;
      int t = e.to;
      int c = e.cost;
      if (t == r) continue;
      if (onCycle[s] && onCycle[t]) continue;
      if (onCycle[t]) {
        c -= minCost[t];
        t = v;
      }
      if (onCycle[s]) s = v;
      newG[i].emplace_back(s,t,c);
    }
  }
  ans += dfs(newG,r);

  return ans;
}

int main() {
  int v, e, r;
  cin >> v >> e >> r;
  vector< vector<Edge> > G(v);
  rep(i,e) {
    int s, t, w;
    cin >> s >> t >> w;
    G[t].emplace_back(s,t,w);
  }

  cout << dfs(G, r) << endl;

  return 0;
}
