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 <vector>
#include <string>
#include <cstring>
#include <algorithm>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30

using namespace std;
typedef long long ll;

struct edge {
    int from,to;
    int cost;

    edge(int t,int c) : to(t),cost(c) {}
    edge(int f,int t,int c) : from(f),to(t),cost(c) {}

    bool operator<(const edge &e) const {
        return cost < e.cost;
    }
};

void backward_traverse(int v,int s,int r,vector<edge> gg[],vector<int> &no,vector<vector<int> > &comp,vector<int> &prev,vector<vector<int> > &next,vector<int> &mcost,vector<int> &mark,int &cost,bool &found,int n) {

    if(mark[v]) {
        vector<int> temp = no;
        found = true;

        do {
            cost += mcost[v];
            v = prev[v];

            if(v != s) {
                while(comp[v].size() > 0) {
                    no[comp[v].back()] = s;
                    comp[s].push_back(comp[v].back());
                    comp[v].pop_back();
                }
            }
        }while(v != s);

        rep(k,comp[s].size()) {
            int j = comp[s][k];
            if(j != r) {
                rep(l,gg[j].size()) {
                    if(no[gg[j][l].from] != s) {
                        gg[j][l].cost -= mcost[temp[j]];
                    }
                }
            }
        }
    }

    mark[v] = true;
    rep(k,next[v].size()) {
        int i = next[v][k];
        if(no[i] != no[v] && prev[no[i]] == v) {
            if(!mark[no[i]] || i == s) {
                backward_traverse(i,s,r,gg,no,comp,prev,next,mcost,mark,cost,found,n);
            }
        }
    }
}

int minimum_spanning_arborescence(vector<edge> G[],int n,int r) {
    vector<edge> gg[n];

    rep(i,n) {
        rep(j,G[i].size()) {
            edge e = G[i][j];
            gg[e.to].push_back(e);
        }
    }

    vector<int> no(n);
    vector<vector<int> > comp(n);

    rep(i,n) {
        no[i] = i;
        comp[i].push_back(i);
    }

    int cost = 0;
    while(true) {
        vector<int> prev(n,-1);
        vector<int> mcost(n,INF);

        rep(j,n) {
            if(j == r) continue;

            rep(k,gg[j].size()) {
                int i = gg[j][k].from;

                if(no[i] != no[j]) {
                    if(gg[j][k].cost < mcost[no[j]]) {
                        mcost[no[j]] = gg[j][k].cost;
                        prev[no[j]] = no[i];
                    }
                }
            }
        }

        vector<vector<int> > next(n);
        rep(i,n) {
            if(prev[i] >= 0) {
                next[prev[i]].push_back(i);
            }
        }

        bool stop = true;
        vector<int> mark(n);
        rep(i,n) {
            if(i == r || mark[i] || comp[i].size() == 0) continue;
            
            bool found = false;
            backward_traverse(i,i,r,gg,no,comp,prev,next,mcost,mark,cost,found,n);

            if(found) stop = false;
        }

        if(stop) {
            rep(i,n) {
                if(prev[i] >= 0) cost += mcost[i];
            }

            return cost;
        }
    }
}
int main() {
    int n,m,r;
    cin >> n >> m >> r;

    vector<edge> G[n];
    rep(i,m) {
        int s,t,cost;
        cin >> s >> t >> cost;

        G[s].push_back(edge(s,t,cost));
    }

    cout << minimum_spanning_arborescence(G,n,r) << endl;


    return 0;
}