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>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 100;
//const ll INF = (1ll << 31) - 1;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;


void print_line(vector<string> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


class UnionFind {
public:
    // 親の番号を格納する。親だった場合-size
    vector<int> parents;

    UnionFind(int n) {
        parents = vector<int>(n, -1);
    }

    // aがどのグループに属しているか
    int root(int a) {
        if (parents[a] < 0) {
            return a;
        }
        return parents[a] = root(parents[a]);
    }

    int size(int a) {
        return -parents[root(a)];
    }

    // aとbをくっつける
    bool connect(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra == rb) {
            return false;
        }
        // 大きいほうにA
        if (size(ra) < size(rb)) {
            swap(ra, rb);
        }
        parents[ra] += parents[rb];
        parents[rb] = ra;
        return true;
    }

    bool is_union(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        return ra == rb;
    }

};


template<typename T>
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template<typename T>
using Edges = vector<edge<T> >;
template<typename T>
using WeightedGraph = vector<Edges<T> >;
using UnWeightedGraph = vector<vector<int> >;
template<typename T>
using Matrix = vector<vector<T> >;

template<typename T, typename E = T>
struct SkewHeap {
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;

    struct Node {
        T key;
        E lazy;
        Node *l, *r;
    };

    const bool rev;
    const G g;
    const H h;

    SkewHeap(bool rev = false) : g([](const T &a, const E &b) { return a + b; }),
                                 h([](const E &a, const E &b) { return a + b; }), rev(rev) {}

    SkewHeap(const G &g, const H &h, bool rev = false) : g(g), h(h), rev(rev) {}

    Node *propagate(Node *t) {
        if (t->lazy != 0) {
            if (t->l) t->l->lazy = h(t->l->lazy, t->lazy);
            if (t->r) t->r->lazy = h(t->r->lazy, t->lazy);
            t->key = g(t->key, t->lazy);
            t->lazy = 0;
        }
        return t;
    }

    Node *merge(Node *x, Node *y) {
        if (!x || !y) return x ? x : y;
        propagate(x), propagate(y);
        if ((x->key > y->key) ^ rev) swap(x, y);
        x->r = merge(y, x->r);
        swap(x->l, x->r);
        return x;
    }

    void push(Node *&root, const T &key) {
        root = merge(root, new Node({key, 0, nullptr, nullptr}));
    }

    T top(Node *root) {
        return propagate(root)->key;
    }

    T pop(Node *&root) {
        T top = propagate(root)->key;
        auto *temp = root;
        root = merge(root->l, root->r);
        delete temp;
        return top;
    }

    bool empty(Node *root) const {
        return !root;
    }

    void add(Node *root, const E &lazy) {
        if (root) {
            root->lazy = h(root->lazy, lazy);
            propagate(root);
        }
    }

    Node *makeheap() {
        return nullptr;
    }
};

template<typename T>
struct MinimumSpanningTreeArborescence {
    using Pi = pair<T, int>;
    using Heap = SkewHeap<Pi, int>;
    using Node = typename Heap::Node;
    const Edges<T> &es;
    const int V;
    T INF;

    MinimumSpanningTreeArborescence(const Edges<T> &es, int V) :
            INF(numeric_limits<T>::max()), es(es), V(V) {}

    T build(int start) {
        auto g = [](const Pi &a, const T &b) { return Pi(a.first + b, a.second); };
        auto h = [](const T &a, const T &b) { return a + b; };
        Heap heap(g, h);
        vector<Node *> heaps(V, heap.makeheap());
        for (auto &e : es) heap.push(heaps[e.to], {e.cost, e.src});
        UnionFind uf(V);
        vector<int> used(V, -1);
        used[start] = start;

        T ret = 0;
        for (int s = 0; s < V; s++) {
            stack<int> path;
            for (int u = s; used[u] < 0;) {
                path.push(u);
                used[u] = s;
                if (heap.empty(heaps[u])) return -1;
                auto p = heap.top(heaps[u]);
                ret += p.first;
                heap.add(heaps[u], -p.first);
                heap.pop(heaps[u]);
                int v = uf.root(p.second);
                if (used[v] == s) {
                    int w;
                    Node *nextheap = heap.makeheap();
                    do {
                        w = path.top();
                        path.pop();
                        nextheap = heap.merge(nextheap, heaps[w]);
                    } while (uf.connect(v, w));
                    heaps[uf.root(v)] = nextheap;
                    used[uf.root(v)] = -1;
                }
                u = uf.root(v);
            }
        }
        return ret;
    }
};

int main() {
    int v, e, r;
    cin >> v >> e >> r;

    vector<edge<ll>> edges;


    MinimumSpanningTreeArborescence<ll> msta(edges, v);

    rep(i, e) {
        ll f, t, c;
        cin >> f >> t >> c;
        edge<ll> ed(f, t, c);
        edges.push_back(ed);
    }
    cout << msta.build(r) << endl;

}



