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;

struct Graph {
  int n;
  int time;
  vector<vector<int>> g;
  vector<int> num, low, group, backPath;
  vector<vector<int>> scc;
  stack<int, deque<int>> S;
  vector<bool> inS;

  Graph(int n)
      : n(n), g(n), num(n, -1), low(n, -1), inS(n, false),
        group(n, 0), backPath(n) {}

  void addEdge(int u, int v) {
    g[u].push_back(v);
  }
  void dfs(int u) {
    num[u] = low[u] = time++;
    S.push(u);
    inS[u] = true;
    for (auto&& v : g[u]) {
      if (num[v] == -1) {
        dfs(v);
        low[u] = min(low[u], low[v]);
      } else if (inS[v]) {
        low[u] = min(low[u], num[v]);
      }
    }
    if (low[u] == num[u]) {
      scc.push_back({});
      while (true) {
        int v = S.top(); S.pop();
        inS[v] = false;
        scc.back().push_back(v);

        group[v] = scc.size() - 1;
        if (u == v) break;
      }
      for (int i = 0, m = scc.back().size(); i < m; ++i) {
        backPath[scc.back()[i]] = scc.back()[(i + 1) % m];
      }
    }
  }
  void stronglyConnectedComponents() {
    for (int i = 0; i < n; ++i) {
      if (num[i] == -1) dfs(i);
    }
  }
};

const int INF = 1e9;

int n, r;

int solve(Graph& g, vector<vector<int>>& adj) {
  int m = adj.size();
  int res = 0;

  for (int i = 0; i < m; ++i) {
    if (i == r) continue;
    int minVal = INF, minId = 0;
    for (int j = 0; j < m; ++j) {
      if (minVal > adj[j][i]) {
        minVal = adj[j][i];
        minId = j;
      }
    }
    res += minVal;
    g.addEdge(minId, i);
  }
  g.stronglyConnectedComponents();
  if (g.scc.size() == m) return res;

  int sz = g.scc.size();
  vector<vector<int>> mat(sz, vector<int>(sz, INF));
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < m; ++j) {
      if (i == j || adj[i][j] == INF) continue;
      int u = g.group[i];
      int v = g.group[j];
      if (u == v) continue;

      mat[u][v] = min(mat[u][v],
          adj[i][j] - (j != g.backPath[j]) * adj[g.backPath[j]][j]);
    }
  }

  res = 0;
  for (int i = 0; i < sz; ++i) {
    if (g.scc[i].size() == 1) continue;
    for (int j = 0, k = g.scc[i].size(); j < k; ++j) {
      res += adj[g.scc[i][(j + 1) % k]][g.scc[i][j]];
    }
  }

  r = g.group[r];
  g.scc.shrink_to_fit();
  g = Graph(sz);
  return res + solve(g, mat);
}

int main() {
  int m; cin >> n >> m >> r;
  vector<vector<int>> adj(n, vector<int>(n, INF));
  while (m--) {
    int s, t, w; cin >> s >> t >> w;
    adj[s][t] = w;
  }
  Graph g(n);
  cout << solve(g, adj) << endl;
  return 0;
}

