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>

using namespace std;

using edge = pair<int, pair<int, int>>;

int INF = 1 << 30;

int Edmonds(const vector<edge> &G, int V, int r) {
    vector<pair<int, int>> MIN(V, pair<int, int>(INF, -1));
    for (auto &e : G) {
        MIN[e.second.second] = min(MIN[e.second.second],
                                   pair<int, int>(e.first, e.second.first));
    }

    MIN[r] = {-1, -1};

    vector<int> group(V, 0);
    vector<bool> isCycle(V, false);
    int count = 0;

    vector<bool> used(V, false);

    for (int i = 0; i < V; i++) {
        if (used[i]) continue;
        vector<int> chain;
        int now = i;
        while (now != -1 && !used[now]) {
            used[now] = true;
            chain.push_back(now);
            now = MIN[now].second;
        }
        if (now != -1) {
            bool inCycle = false;
            for (int j : chain) {
                group[j] = count;
                if (j == now) {
                    isCycle[count] = true;
                    inCycle = true;
                }
                if (!inCycle)
                    count++;
            }
            if (inCycle)
                count++;
        } else {
            for (int j : chain) {
                group[j] = count;
                count++;
            }
        }
    }
    int res = 0;
    if (count == V) {
        for (int i = 0; i < V; i++) {
            if (i == r) continue;
            res += MIN[i].first;
        }
        return res;
    }

    for (int i = 0; i < V; i++) {
        if (i == r) continue;
        if (isCycle[group[i]])
            res += MIN[i].first;
    }

    vector<edge> nG;
    for (auto &e : G) {
        int to = e.second.second;
        int gfrom = group[e.second.first];
        int gto = group[e.second.second];
        if (gfrom == gto) continue;
        else if (isCycle[gto])
            nG.push_back({e.first - MIN[to].first, {gfrom, gto}});
        else {
            nG.push_back({e.first, {gfrom, gto}});
        }
    }
    return res + Edmonds(nG, count, group[r]);
}


int main() {
    int V, E, r;
    cin >> V >> E >> r;
    vector<edge> G;

    for (int i = 0; i < E; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        G.push_back({w, {s, t}});
    }
    auto res = Edmonds(G, V, r);
    cout << res << endl;

    return 0;
}

