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 <cstdio>
#include <cassert>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

struct Edge {
    int from, to, cost;
    Edge(){}
    Edge(int from, int to, int cost) : from(from), to(to), cost(cost){}
    bool operator < (const Edge &rhs) const {
        return (cost < rhs.cost);
    }
    bool operator > (const Edge &rhs) const {
        return (rhs < *this);
    }
};

int directed_MST(vector<Edge> &G, int N, int r)
{
    vector<Edge> mini(N, Edge(-1, -1, 1000000));

    for (int i = 0; i < G.size(); i++){
        mini[G[i].to] = min(mini[G[i].to], G[i]);
    }

    mini[r] = Edge(-1, -1, -1);

    vector<int> gr(N, 0);
    vector<bool> isCycle(N, false);
    vector<bool> visited(N, false);
    int ct = 0;

    for (int i = 0; i < N; i++){
        if (visited[i]) continue;

        vector<int> chain;
        int v = i;
        while (v != -1 && !visited[v]){
            visited[v] = true;
            chain.push_back(v);
            v = mini[v].from;
        }

        if (v != -1){
            bool inCycle = false;
            for (int j = 0; j < chain.size(); j++){
                gr[chain[j]] = ct;
                if (chain[j] == v){
                    isCycle[ct] = true;
                    inCycle = true;
                }
                if (!inCycle) ct++;
            }
            ct += inCycle;
        }
        else {
            for (int j = 0; j < chain.size(); j++){
                gr[chain[j]] = ct++;
            }
        }
    }

    if (ct == N){
        int ans = 0;
        for (int i = 0; i < N; i++){
            if (i != r) ans += mini[i].cost;
        }
        return (ans);
    }

    int ans = 0;

    for (int i = 0; i < N; i++){
        if (i != r && isCycle[gr[i]]) ans += mini[i].cost;
    }

    vector<Edge> nG;
    for (int i = 0; i < G.size(); i++){
        int f2 = gr[G[i].from], t2 = gr[G[i].to];
        if (f2 == t2) continue;
        else if (isCycle[t2]){
            nG.push_back(Edge(f2, t2, G[i].cost - mini[G[i].to].cost));
        }
        else {
            nG.push_back(Edge(f2, t2, G[i].cost));
        }
    }

    return (ans + directed_MST(nG, ct, gr[r]));
}

int main()
{
    int n, m, s;
    set< pair<int, int> > dup;
    vector<Edge> G;

    scanf("%d %d %d", &n, &m, &s);

    for (int i = 0; i < m; i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        G.push_back(Edge(x, y, z));
    }

    printf("%d\n", directed_MST(G, n, s));

    return (0);
}

