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;

using i64 = int64_t;

using Weight = int;

struct Edge{
    int from, to;
    Weight weight;
};

using Graph = vector<vector<Edge>>;

constexpr Weight INF = 1e9;

Graph chu_liu_edmonds(const Graph &graph, const int root) {
    const int n = graph.size();

    // 頂点vに入る重み最小の辺でグラフを構築
    vector<Weight> min_weight(n, INF), prev(n, -1);
    for(int v=0;v<n;v++) {
        for(auto &e: graph[v]) {
            if(e.weight < min_weight[e.to]) {
                min_weight[e.to] = e.weight;
                prev[e.to] = v;
            }
        }
    }

    // 閉路の検出
    int cycle = -1;
    vector<int> groups(n), used(n, -1);
    iota(groups.begin(), groups.end(), 0);
    for(int v=0;v<n;v++) {
        if(used[v] != -1 || prev[v] == -1 || v == root) continue;

        int cur = v;
        do{
            used[cur] = v;
            cur = prev[cur];
        }while(cur != root && cur != -1 && used[cur] == -1);

        if(used[cur] != v)continue;
        cycle = cur;
        groups[cur] = cur;
        for(int u=prev[cur];u!=cur;u=prev[u])groups[u] = cur;
        break;
    }

    Graph res(n);
    if(cycle == -1) { // 閉路なし
        for(int v=0;v<n;v++) {
            if(prev[v] == -1 || v == root)continue;
            res[prev[v]].push_back({prev[v], v, min_weight[v]});
        }
    }else{ // 閉路あり
        Graph g(n);
        using E = tuple<int, int, Weight>;
        map<E, Edge> mp;
        for(int v=0;v<n;v++) {
            for(auto e: graph[v]) {
                int from = groups[v], to = groups[e.to], w = e.weight;
                if(from == to)continue;
                if(to == cycle)w -= min_weight[e.to];
                g[from].push_back({from, to, w});
                mp[E{from, to, w}] = {v, e.to, e.weight};
            }
        }

        Graph tree = chu_liu_edmonds(g, groups[root]);

        int u;
        for(int v=0;v<n;v++) {
            for(auto e: tree[v]) {
                Edge origin = mp[E{e.from, e.to, e.weight}];
                if(e.to == cycle)u = origin.to;
                res[origin.from].push_back(origin);
            }
        }

        for(int v=0;v<n;v++) {
            if(groups[v] != cycle || v == u)continue;
            res[v].push_back({prev[v], v, min_weight[v]});
        }
    }

    return res;
}

int main(){
    int v, e, r;
    cin >> v >> e >> r;
    Graph graph(v, vector<Edge>());
    for(int i=0;i<e;++i){
        int s, t, w;
        cin >> s >> t >> w;
        graph[s].push_back({s, t, w});
    }
    auto res = chu_liu_edmonds(graph, r);

    int ans = 0;
    for(int i=0;i<v;++i){
        for(auto edge: res[i]){
            ans += edge.weight;
        }
    }

    cout << ans << endl;

    return 0;
}

