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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;
//最小全域有向木(O(mlogn))
//joisinoさんのブログを参照
//http://joisino.hatenablog.com/entry/2017/01/11/230141
class UF {
private:
    int sz; vector<int> par;
public:
    UF(){}
    UF(int node_size){
        sz = node_size;
        par.resize(sz);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x,int y){
        x = find(x), y = find(y);
        if(x == y) return;
    	par[x] = y;
    }
    bool same(int x,int y){
        return find(x) == find(y);
    }
};

template<typename T> class LazyHeap {
public:
    struct node{
        node *l, *r;
        T val, add;
        int id;
        node(T t, int i) : l(nullptr), r(nullptr), val(t), add(0), id(i){}
    };
    void lazy(node* a){
        if(a->l) a->l->add += a->add;
        if(a->r) a->r->add += a->add;
        a->val += a->add;
        a->add = 0;
    }
    node* meld(node* a, node* b){
        if(!a) return b; if(!b) return a;
        if(a->val+a->add > b->val+b->add) swap(a, b);
        lazy(a);
        a->r = meld(a->r,b);
        swap(a->l, a->r);
        return a;
    }
    node* push(node* org, T val, int i){
        node* p = new node(val, i);
        return meld(org, p);
    }
    node* pop(node* p){
        lazy(p);
        return meld(p->l, p->r);
    }
};

template<typename T> class Arborescence {
public:
    struct edge{
        int from, to;
        T cost;
    };
    LazyHeap<T> heap;
    vector<edge> es;
    vector<int> used, from, from_cost;
    vector<typename LazyHeap<T>::node*> come;
    int V;
    Arborescence(int node_size){
        V = node_size;
        used.resize(V, 0), from.resize(V), from_cost.resize(V);
        come.resize(V, nullptr);
    }
    void add_edge(int u, int v, T cost){
        es.push_back((edge){u,v,cost});
    }
    //rを根とする最小全域有向木のコストを計算
    T solve(int r){
        used[r] = 2;
        UF uf(V);
        rep(i,(int)es.size()){
            edge& e = es[i];
            come[e.to] = heap.push(come[e.to], e.cost, i);
        }
        T ans = 0;
        rep(i,V){
            if(used[i] != 0) continue;
            int cur = i;
            vector<int> path;
            while(used[cur] != 2){
                used[cur] = 1;
                path.push_back(cur);
                //全域有向木が存在しない場合
                if(!come[cur]) return numeric_limits<T>::max();
                from[cur] = uf.find(es[come[cur]->id].from);
                from_cost[cur] = come[cur]->val + come[cur]->add;
                come[cur] = heap.pop(come[cur]);
                if(from[cur] == cur) continue;
                ans += from_cost[cur];
                if(used[from[cur]] == 1){
                    int p = cur;
                    do{
                        if(come[p]){
                            come[p]->add -= from_cost[p];
                        }
                        if(p != cur){
                            uf.unite(p,cur);
                            come[cur] = heap.meld(come[cur],come[p]);
                        }
                        p = uf.find(from[p]);
                    }while(p != cur);
                }else{
                    cur = from[cur];
                }
            }
            for(int v : path){
                used[v] = 2;
            }
        }
        return ans;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,r;
    cin >> n >> m >> r;
    Arborescence<int> ar(n);
    rep(i,m){
        int a,b,c;
        cin >> a >> b >> c;
        ar.add_edge(a,b,c);
    }
    cout << ar.solve(r) << "\n";
    return 0;
}

