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 <vector>

using namespace std;

using Weight=long long;
static const Weight INF=1LL<<57;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

void visit(
    Graph &h, size_t v, size_t s, size_t r, vector<size_t> &no,
    vector<vector<size_t>> &comp, vector<size_t> &prev,
    vector<vector<size_t>> &next, vector<Weight> &mcost, vector<bool> &mark,
    Weight &cost, bool &found
) {
    if (mark[v]) {
        vector<size_t> tmp=no;
        found = true;
        do {
            cost += mcost[v];
            v = prev[v];
            if (v != s) {
                while (!comp[v].empty()) {
                    no[comp[v].back()] = s;
                    comp[s].push_back(comp[v].back());
                    comp[v].pop_back();
                }
            }
        } while (v != s);
        
        for (size_t j: comp[s])
            if (j != r)
                for (Edge &e: h[j])
                    if (no[e.src] != s)
                        e.weight -= mcost[tmp[j]];
    }

    mark[v] = true;
    for (size_t i: next[v]) if ((no[i] != no[v]) && (prev[no[i]] == v))
        if (!mark[no[i]] || i == s)
            visit(h, i, s, r, no, comp, prev, next, mcost, mark, cost, found);
}

Weight minspan_arborescence(const Graph &g, size_t r) {
    const size_t V=g.size();
    Graph h(V);
    for (size_t u=0; u<V; ++u)
        for (const Edge &e: g[u])
            h[e.dst].push_back(e);

    vector<size_t> no(V);
    vector<vector<size_t>> comp(V);
    for (size_t u=0; u<V; ++u)
        comp[u].push_back(no[u]=u);

    for (Weight cost=0; true;) {
        vector<size_t> prev(V, -1);
        vector<Weight> mcost(V, INF);

        for (size_t j=0; j<V; ++j) if (j != r)
            for (const Edge &e: h[j])
                if (no[e.src] != no[j] && e.weight < mcost[no[j]]) {
                    mcost[no[j]] = e.weight;
                    prev[no[j]] = no[e.src];
                }

        vector<vector<size_t>> next(V);
        for (size_t u=0; u<V; ++u) if (~prev[u])
            next[prev[u]].push_back(u);

        bool stop=true;
        vector<bool> mark(V);
        for (size_t u=0; u<V; ++u)
            if ((u != r) && !mark[u] && !comp[u].empty()) {
                bool found=false;
                visit(
                    h, u, u, r, no, comp, prev, next, mcost, mark, cost, found
                );

                if (found) stop = false;
            }

        if (!stop) continue;

        for (size_t u=0; u<V; ++u)
            if (~prev[u])
                cost += mcost[u];

        return cost;
    }
}

int main() {
    size_t V, E, r;
    scanf("%zu %zu %zu", &V, &E, &r);

    Graph g(V);
    for (size_t i=0; i<E; ++i) {
        size_t s, t;
        Weight w;
        scanf("%zu %zu %lld", &s, &t, &w);

        connect(g, s, t, w);
    }

    printf("%lld\n", minspan_arborescence(g, r));
    return 0;
}