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 weight = int;
constexpr weight INF = 1e9;

struct edge {
    int from, to;
    weight cost;
    
    bool operator<(edge const& e) const {
        return cost < e.cost;
    }
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, weight cost) {
    g[from].push_back(edge{from, to, cost});
}

int scc(std::vector<std::vector<int>>& G, std::vector<int>& cmp) {
    int V = G.size();
    std::vector<std::vector<int>> g(V), rg(V);
    std::vector<bool> used(V, false);
    std::vector<int> vs;
    cmp.resize(V);
    for(int i = 0; i < V; ++i) {
        for(auto to : G[i]) {
            g[i].push_back(to);
            rg[to].push_back(i);
        }
    }
    std::function<void(int)> dfs = [&g, &vs, &used, &dfs](int v) {
        used[v] = true;
        for(auto i : g[v]) {
            if(!used[i]) {
                dfs(i);
            }
        }
        vs.push_back(v);
    };
    std::function<void(int, int)> rdfs = [&rg, &cmp, &used, &rdfs](int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for(int i : rg[v]) {
            if(!used[i]) {
                rdfs(i, k);
            }
        }
    };
    for(int v=0; v<V; ++v) {
        if(!used[v]) {
            dfs(v);
        }
    }
    std::fill(used.begin(), used.end(), false);
    int k = 0;
    for(int i=vs.size()-1; i>=0; --i) {
        if(!used[vs[i]]) {
            rdfs(vs[i], k++);
        }
    }
    return k;
}

std::vector<std::vector<int>> build_graph(std::vector<std::vector<int>> const& g, std::vector<int> const& cmp, int K) {
    int V = g.size();
    std::vector<std::set<int>> s(K);
    std::vector<std::vector<int>> res(K);
    for(int i = 0; i < V; ++i) {
        for(auto to : g[i]) {
            s[cmp[i]].insert(cmp[to]);
        }
    }
    for(int i = 0; i < K; ++i) {
        for(auto j : s[i]) {
            if(i != j) {
                res[i].push_back(j);
            }
        }
    }
    return res;
}


weight minimum_spanning_arborescence(graph const& g, int root, weight sum = 0) {
    int const n = g.size();

    std::vector<int> rev(n, -1), cost(n, INF);
    for(int i = 0; i < n; ++i) {
        for(auto& e : g[i]) {
            if(e.cost < cost[e.to]) {
                cost[e.to] = e.cost;
                rev[e.to] = i;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        if(i != root && rev[i] == -1) { // not exists
            return INF;
        }
    }

    std::vector<std::vector<int>> g2(n);
    for(int i = 0; i < n; ++i) {
        if(root == i) {
            continue;
        }
        g2[rev[i]].push_back(i);
        sum += cost[i];
    }
    std::vector<int> cmp(n);
    int const K = scc(g2, cmp);
    auto nxt = build_graph(g2, cmp, K);
    if(nxt.size() == n) {
        return sum;
    }

    graph ng(nxt.size());
    for(int i = 0; i < n; ++i) {
        for(auto& e : g[i]) {
            if(cmp[i] == cmp[e.to]) {
                continue;
            }
            ng[cmp[i]].push_back(edge{cmp[i], cmp[e.to], e.cost - cost[e.to]});
        }
    }

    return minimum_spanning_arborescence(ng, cmp[root], sum);
}

int main() {
    int V, E, r;
    std::cin >> V >> E >> r;
    graph g(V);
    for(int i = 0; i < E; ++i) {
        int s, t, w;
        std::cin >> s >> t >> w;
        add_edge(g, s, t, w);
    }
    std::cout << minimum_spanning_arborescence(g, r) << std::endl;
}
