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<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
#include<complex>
using namespace std;

const int INF = INT_MAX;

struct Edge{
    int dst;
    int weight;
    Edge(int dst, int weight): dst(dst), weight(weight) {}
    bool operator<( const Edge& right ) const {
        return weight != right.weight ? weight < right.weight : dst < right.dst;
    }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void printGraph(Graph &G){
    cout << "graph" << endl;
    for (int i=0;i<G.size();i++){
        for (int j=0;j<G[i].size();j++){
            cout << i << " " << G[i][j].dst << " " << G[i][j].weight <<endl;
        }
    }
}

void printVector(vector<int> &v){
    cout << "vector" << endl;
    for (int i=0;i<v.size();i++){
        cout << v[i] << " " ;
    }
    cout << endl;
}

Graph reverse(Graph &G){
    Graph RG(G.size());
    for (int i=0;i<G.size();i++){
        for (int j=0;j<G[i].size();j++){
            Edge e(i, G[i][j].weight);
            RG[G[i][j].dst].push_back(e);
        }
    }
    return RG;
}

int reverseCycleDetect(Graph &G, int s, vector<int> &used, vector<int> &cycle){
    if(used[s]==1){
        return 0;
    }
    used[s]=2;
    for (int i=0;i<G[s].size();i++){
        if(used[G[s][i].dst]==2){
            cycle.push_back(G[s][i].dst);
            return 1;
        }
        if(used[G[s][i].dst]==0){
            int judge = reverseCycleDetect(G, G[s][i].dst, used, cycle);
            if(judge == 1){
                if(cycle[0] != G[s][i].dst){
                    cycle.push_back(G[s][i].dst);
                    return 1;
                }else{
                    return 2;
                }
            }else if(judge == 2){
                return 2;
            }
        }
    }
    used[s]=1;
    return 0;
}

vector<int> cycleDetect(Graph &G){
    vector<int> used(G.size(), 0);
    vector<int> cycle;

    for (int i=0;i<G.size();i++){
        reverseCycleDetect(G, i, used, cycle);
        if(!cycle.empty()) break;
    }
    reverse(cycle.begin(), cycle.end());
    return cycle;
}

int findWeight(Graph &G, int from, int dest){
    int i = 0;
    while(G[from][i].dst != dest){
        i++;
    }
    return G[from][i].weight;
}

int findVector(vector<int> &v, int x){
    for (int i=0;i<v.size();i++){
        if (v[i] == x) return i;
    }
    return -1;
}

int ChuLiu(Graph &G, int r){
    Graph H(G.size());
    Graph RG = reverse(G);
    for (int i=0;i<G.size();i++){
        if(i != r && !RG[i].empty()){
            Edge e = *min_element(RG[i].begin(), RG[i].end());
            Edge f(i, e.weight);
            H[e.dst].push_back(f);
        }
    }

    vector<int> cycle = cycleDetect(H);
    if(cycle.empty()){
        int S = 0;
        for(int i=0;i<H.size();i++){
            for (int j=0;j<H[i].size();j++){
                S += H[i][j].weight;
            }
        }
        return S;
    }else{
        int S = 0;
        for (int i=0;i<cycle.size();i++){
            S += findWeight(H, cycle[i], cycle[(i+1)%cycle.size()]);
        }

        //printVector(cycle);
        Graph K(G.size()+1);
        for (int i=0;i<G.size();i++){
            for(int j=0;j<G[i].size();j++){

                //cout << "from: " << i << "dest: " << G[i][j].dst << endl;

                int b1 = findVector(cycle, i);
                int b2 = findVector(cycle, G[i][j].dst);

                //cout << b1 << " " << b2 <<endl;

                if(b1 == -1 && b2 == -1){
                    K[i].push_back(G[i][j]);
                }else if(b1 == -1 && b2 != -1){
                    int w = G[i][j].weight;
                    int dest = cycle[b2];
                    int from = cycle[(b2-1+cycle.size())%cycle.size()];
                    //cout << from << " " << dest <<endl;
                    w -= findWeight(H, from, dest);
                    Edge e(G.size(), w);
                    K[i].push_back(e);
                }else if(b1 != -1 && b2 == -1){
                    K[G.size()].push_back(G[i][j]);
                }
            }
        }
        //printGraph(K);
        return ChuLiu(K, r) + S;
    }
}

int main(){
    int V, E, r;
    cin >> V >> E >> r;
    Graph G(V);
    for(int i=0;i<E;i++){
        int s, t, w;
        cin >> s >> t >> w;
        Edge e(t, w);
        G[s].push_back(e);
    }

    cout << ChuLiu(G, r) << endl;

    return 0;
}