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<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e18+7;
const ll MOD=1000000007;

template<typename T>
class Chu_Liu{
private:
    typedef pair<T,ll> edge; //cost,from
    vector<vector<edge>> E;
    ll V;
    T err;
    
    
public:
    Chu_Liu(ll V,T err):V(V),err(err){E.resize(V);}
    
    void add_edge(ll from,ll to,T cost){E[to].push_back({cost,from});}
    
    void sort_edge(vector<vector<edge>> &e){
        for(int i=0;i<e.size();i++){sort(e[i].begin(),e[i].end());}
    }
    
    T search(ll root){return search(root,V,E);}
    
    T search(ll root,ll v,vector<vector<edge>> e){
        if(v<=1){return (T)0;}
        vector<edge> mins(v,{(T)0,root});
        vector<ll> group(v);
        vector<bool> closed(v,false);
        T cost=0;
        ll count=1;
        for(int i=0;i<v;i++){group[i]=i+1;}
        group[root]=0;
        sort_edge(e);
        for(int i=0;i<v;i++){
            if(i==root){continue;}
            assert(e[i].size()>0);
            mins[i]=e[i][0];
        }
        
        vector<bool> used(v,false);
        used[root]=true;
        for(int i=0;i<v;i++){
            if(used[i]){continue;}
            vector<ll> chain;
            ll where=i;
            set<ll> done;
            while(!used[where]){
                done.insert(where);
                chain.push_back(where);
                used[where]=true;
                where=mins[where].S;
            }
            if(group[where]==0){
                for(int t=0;t<chain.size();t++){
                    group[chain[t]]=0;
                    cost+=mins[chain[t]].F;
                }
            }
            else if(done.find(where)!=done.end()){
                bool in_cycle=false;
                for(int t=0;t<chain.size();t++){
                    if(chain[t]==where){in_cycle=true;}
                    group[chain[t]]=count;
                    if(!in_cycle){count++;}
                    if(in_cycle){
                        closed[chain[t]]=true;
                        cost+=mins[chain[t]].F;
                    }
                }
                count++;
            }
            else{
                for(int t=0;t<chain.size();t++){
                    group[chain[t]]=count;
                    count++;
                }
            }
        }
        
        vector<vector<edge>> new_edge;
        new_edge.resize(count);
        for(int i=0;i<v;i++){
            if(group[i]==0){continue;}
            if(!closed[i]){
                for(int t=0;t<e[i].size();t++){
                    if(group[e[i][t].S]==group[i]){continue;}
                    e[i][t].S=group[e[i][t].S];
                    new_edge[group[i]].push_back(e[i][t]);
                }
                continue;
            }
            for(int t=1;t<e[i].size();t++){
                if(group[e[i][t].S]==group[i]){continue;}
                e[i][t].F-=mins[i].F;
                e[i][t].S=group[e[i][t].S];
                new_edge[group[i]].push_back(e[i][t]);
            }
        }
        cost+=search(0,count,new_edge);
        return cost;
    }
};


int main(){
    ll v,e,r;
    cin>>v>>e>>r;
    Chu_Liu<ll> C(v,E);
    for(int i=0;i<e;i++){
        ll s,t,c;
        cin>>s>>t>>c;
        C.add_edge(s,t,c);
    }
    cout<<C.search(r)<<endl;
    
    
    return 0;
}

