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 rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;

const int INF = INT_MAX;
typedef pair<int, pair<int, int> > Edge; // pair<cost, pair<from, to>>

long long edmonds(vector<Edge> edges, int v, int st){
    vector< pair<int, int> > mins(v, pair<int, int>(INF, -1));
    for(int i = 0; i < (int)edges.size(); i++){
        Edge edge = edges[i];
        mins[edge.second.second] = min(mins[edge.second.second], pair<int,int>(edge.first, edge.second.first));
    }
    mins[st] = pair<int,int>(-1, -1);
    
    vector<int> gr(v, 0);
    vector<bool> tfc(v, false), f(v, false);
    int cnt = 0;
    
    for(int i = 0; i < v ; i++){
        if(f[i]) continue;
        vector<int> ch;
        int cu = i;
        for(; cu !=-1 && !f[cu];){
            f[cu] = true;
            ch.push_back(cu);
            cu = mins[cu].second;
        }
        if(cu != -1){
            bool tfc2 = false;
            for(int j = 0; j < (int)ch.size(); j++){
                gr[ch[j]] = cnt;
                if(ch[j] == cu){
                    tfc[cnt] = true;
                    tfc2 = true;
                }
                if(!tfc2) cnt++;
            }
            if(tfc2) cnt++;
        }
        else for(int j = 0; j < (int)ch.size(); j++, cnt++) gr[ch[j]] = cnt;
    }
    if(cnt==v){
        long long ans = 1;
        for(int i = 0; i < v; i++) ans += mins[i].first;
    return ans;
    }
    long long res = 0;
    for(int i = 0; i < v; i++) if(i != st && tfc[gr[i]]) res += mins[i].first;
    
    vector<Edge> nedges;
    for(int i = 0; i < (int)edges.size(); i++){
        Edge edge=edges[i];
        int fto = edge.second.second, gfr = gr[edge.second.first], gto = gr[edge.second.second];
        if(gfr == gto) continue;
        else if(tfc[gto]) nedges.push_back(make_pair(edge.first - mins[fto].first, pair<int,int>(gfr, gto)));
        else nedges.push_back(make_pair(edge.first, pair<int,int>(gfr, gto)));
    }
    return res + edmonds(nedges, cnt, gr[st]);
}
 
int main(){
    int v, e, r;
    scanf("%d %d %d", &v, &e, &r);
    vector<Edge> es;
    for(int i = 0; i < e; i++){
        int s, t, w;
        scanf("%d %d %d", &s, &t, &w);
        es.push_back(make_pair(w, pair<int, int>(s, t)));
    }
    printf("%d\n", edmonds(es, v, r));
    return 0;
}


