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;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(2e4) + 5;
constexpr double EPS = 1e-8;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()


struct Edge
{
    int from, to;
    int64_t weight;
    Edge(){};
    Edge(int u, int v, int64_t w){
        from = u;
        to = v;
        weight = w;
    };
};
bool operator < (const Edge &e, const Edge &f){
    if(e.weight != f.weight){
        return e.weight < f.weight;
    }
    else if(e.from != f.from){
        return e.from < f.from;
    }
    else{
        return e.to < f.to;
    }
}

bool operator > (const Edge &e, const Edge &f){
    if(e.weight != f.weight){
        return e.weight > f.weight;
    }
    else if(e.from != f.from){
        return e.from > f.from;
    }
    else{
        return e.to > f.to;
    }
}

// 最小有向全域木
struct ChuLiu_Edmonds
{
    int N, root;
    vector< vector< Edge > > g, gr;
    vector<bool> onCycle, visited;
    vector< Edge > minEdge;

    ChuLiu_Edmonds(){};
    ChuLiu_Edmonds(int siz, int r){init(siz, r);}
    void init(int siz, int r){
        N = siz;
        root = r;
        g.clear();
        g.resize(N);
        gr.clear();
        gr.resize(N);
        onCycle.resize(N);
        visited.resize(N);
        minEdge.resize(N);
    }
    void addEdge(int from, int to, int64_t weight){
        if(from == to)return;
        g[from].push_back(Edge(from, to, weight));
        gr[to].push_back(Edge(from, to, weight));
    }

    // 閉路を縮約した新たなグラフを構築し、再帰的に解を得る
    int64_t rec(int v){
        ChuLiu_Edmonds sub(N, root);
        auto getIndex = [&](int u){return onCycle[u] ? v : u;};
        for(int u=0;u<N;u++){
            for(auto &e : gr[u]){
                sub.addEdge(getIndex(e.from), getIndex(e.to), e.weight - (onCycle[u] ? minEdge[u].weight : 0));
            }
        }
        int64_t res = sub.build();
        return res;
    }

    int64_t build(){
        fill(onCycle.begin(), onCycle.end(), false);
        fill(visited.begin(), visited.end(), false);

        // 頂点iへの辺のうち最小コストの辺を得る
        for(int i=0;i<N;i++){
            if(i==root || gr[i].size()==0)continue;
            sort(gr[i].begin(), gr[i].end());
            minEdge[i] = gr[i][0];
        }
        
        // 閉路検出
        vector<int> deg(N, 0);
        queue<int> que;
        for(int i=0;i<N;i++){
            if(i==root || gr[i].size()==0)continue;
            deg[minEdge[i].from]++;
        }
        for(int i=0;i<N;i++){
            if(i==root || gr[i].size()==0)continue;
            if(deg[i]==0) que.push(i);
        }
        while(!que.empty()){  // 出次数0の頂点から取り除く
            int v = que.front();
            que.pop();
            if(gr[v].size()>0){
                int pre = minEdge[v].from;
                deg[pre]--;
                if(pre != root && deg[pre]==0) que.push(pre);
            }
        }
        for(int i=0;i<N;i++){
            if(deg[i] > 0){  // 閉路がある
                onCycle[i] = true;
                int pre = minEdge[i].from;
                while(pre != i){
                    onCycle[pre] = true;
                    pre = minEdge[pre].from;
                }
                int64_t sum = 0;
                sum += rec(i);
                for(int j=0;j<N;j++){
                    if(onCycle[j]) sum += minEdge[j].weight;
                }
                return sum;
            }
        }
        // 閉路がない
        int64_t res = 0;
        for(int i=0;i<N;i++){
            if(i==root || gr[i].size()==0)continue;
            res += minEdge[i].weight;
        }
        return res;
    }
};


ChuLiu_Edmonds graph;

int main() {
    int V, E, r;
    cin >> V >> E >> r;
    graph.init(V, r);
    for(int i=0;i<E;i++){
        int u, v;
        int64_t w;
        cin >> u >> v >> w;
        graph.addEdge(u, v, w);
    }
    cout << graph.build() << endl;
    return 0;
}

