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 <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> P;//weight,from

struct vertex{
    vector<P> IN;
};

#define MAX_E 1000
#define MAX_V 100
#define MAX_w 10000

bool isUsed[MAX_V*2];

void erase(int s, int t, vector<vertex>& V){
    for(auto ite=V[t].IN.begin();ite!=V[t].IN.end();ite++){
        if(ite->second==s){
            V[t].IN.erase(ite);
            return;
        }
    }
}

void add(int s, int t, int w, vector<vertex>& V){
    V[t].IN.emplace_back(w,s);
}

bool isCircle(int i, bool *isUsed, vector<int>& C, vector<vertex> &V){
    if(isUsed[i]){
        C.push_back(i);
        return true;
    }
    isUsed[i]=true;

    if(V[i].IN.size()>0 && isCircle(V[i].IN[0].second,isUsed,C,V)){
        C.push_back(i);
        return true;
    }
    return false;
}

void edmonds(vector<vertex> &V){
    //???????????????
    vector<int> C;
    for(auto& v:V) sort(v.IN.begin(),v.IN.end());
    for(int i=0;i<V.size();i++){
        C.clear();
        fill(isUsed,isUsed+MAX_V*2,false);
        if(isCircle(i,isUsed,C,V)) break;
    }
    if(C.empty()){
        //???????????????????????????????°??????\?????§??\???????¶????
        for(auto& v:V){
            if(v.IN.size()>1) v.IN.erase(v.IN.begin()+1,v.IN.end());
        }
        return;
    }else{
        for(auto ite=C.begin()+1;ite!=C.end();ite++){
            if(*ite==C[0]){
                //?????¨?????????????????????
                C.erase(ite,C.end());
                //C???(i,i+1)??¨????????§???????????£?????????
                //??????????°????????????????????????§??????????????\???
                break;
            }
        }
    }
    //?????????????????????
    //???????????§?????¨??¨??????
    int c_w[C.size()];
    for(int i=0;i<C.size();i++){
        int prev = (i==0?C.back():C[i-1]);
        for(auto ite=V[C[i]].IN.begin();ite!=V[C[i]].IN.end();ite++){
            if(ite->second==prev){
                c_w[i]=ite->first;
                V[C[i]].IN.erase(ite);
                break;
            }
        }
    }
    //??\??£???????????§?????????
    int INv[V.size()]; //INv[??\??£???????????§????§????]=??????
    fill(INv,INv+V.size(),-1);
    int INw[V.size()]; //INw[??\??£???????????§????§????]=??????
    fill(INw,INw+V.size(),MAX_w+1);
    for(int i=0;i<C.size();i++){
        int v=C[i];
        for(auto&e:V[v].IN){
            int w=e.first-c_w[i], s=e.second;
            if(INw[s]>w){
                INw[s]=w;
                INv[s]=v;
            }
        }
        V[v].IN.clear();
    }
    for(auto& c:C) INv[c]=-1;
    //??????????????§?????????
    int OUTv[V.size()]; //OUTv[???????????£?????§?????????]=?§????
    fill(OUTv,OUTv+V.size(),-1);
    int OUTw[V.size()]; //OUTw[???????????£?????§?????????]=??????
    fill(OUTw,OUTw+V.size(),MAX_w+1);
    for(int i=0;i<V.size();i++){
        for(auto ite=V[i].IN.begin();ite!=V[i].IN.end();NULL){
            int w=ite->first, s=ite->second;
            bool flag = false;
            for(auto& c:C){
                if(c==s){
                    if(OUTw[i]>w){
                        OUTw[i]=w;
                        OUTv[i]=s;
                    }
                    ite=V[i].IN.erase(ite);
                    flag=true;
                    break;
                }
            }
            if(!flag)ite++;
        }
    }

    //vc?????????
    int vc = V.size();
    V.emplace_back();
    //??\??£???????????§???vc??????????????????
    for(int i=0;i<vc;i++){
        if(~INv[i]) add(i,vc,INw[i],V);
    }
    //??????????????§???vc??????????????????
    for(int i=0;i<vc;i++){
        if(~OUTv[i]) add(vc,i,OUTw[i],V);
    }

    //?????°
    edmonds(V);

    //???????????????
    //vc?????\??£?????\?????§???????????????????????????????????¨????????§
    int s=V[vc].IN[0].second, w=V[vc].IN[0].first;
    for(int i=0;i<C.size();i++){
        if(C[i]==INv[s]){
            add(s,INv[s],w+c_w[i],V);
        }
    }
    for(int i=0;i<C.size();i++){
        if(V[C[i]].IN.empty()) add(i==0?C.back():C[i-1],C[i],c_w[i],V);
    }
    //??????????????§???????´??????????
    for(int i=0;i<vc;i++){
        for(auto ite=V[i].IN.begin();ite!=V[i].IN.end();ite++){
            if(ite->second==vc){
                V[i].IN.erase(ite);
                add(OUTv[i],i,OUTw[i],V);
                break;
            }
        }
    }
    //vc????¶????
    V.erase(V.begin()+vc);
    return;
}

int main(){
    vector<vertex> V;
    int nv,ne,r;
    cin>>nv>>ne>>r;
    for(int i=0;i<nv;i++) V.emplace_back();
    for(int i=0;i<ne;i++){
        int s,t,w;
        cin>>s>>t>>w;
        if(t==r)continue;//r?????\?????????????????????
        add(s,t,w,V);
    }

    //????°???¨???????????¨???Chu-Liu/Edmonds?????¢?????´???????????§?±???????
    edmonds(V);

    //?????????????¨?
    int ans=0;
    for(auto& v:V){
        for(auto& e:v.IN){
            ans+=e.first;
        }
    }
    cout<<ans<<endl;
    return 0;
}