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 <iostream>
#include <vector>
#include <algorithm>

template <class Cost = int>
struct Edge {
    int from, to;
    Cost cost;
    Edge(int from = -1, int to = -1, Cost cost = 1)
        : from(from), to(to), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
class Graph {
public:
    int size;
    std::vector<std::vector<Edge<Cost>>> path;

    explicit Graph(int N = 0) : size(N), path(size) {}
    void span(int from, int to, Cost cost = 1) {
        path[from].push_back(Edge<Cost>(from, to, cost));
    }
    std::vector<Edge<Cost>>& operator[](int v) { return path[v]; }
};

template <class Cost = int>
class StronglyConnectedComponents {
private:
    Graph<Cost> graph, rgraph;
    std::vector<bool> visited;
    std::vector<int> order;

    void revinit() {
        rgraph = Graph<Cost>(graph.size);
        for (int v = 0; v < graph.size; ++v) {
            for (const auto& e : graph[v]) {
                rgraph.span(e.to, v);
            }
        }
    }

    void dfs(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (const auto& e : graph[v]) dfs(e.to);
        order.push_back(v);
    }

    void rdfs(int v, int curid) {
        if (id[v] >= 0) return;
        id[v] = curid;
        groups.back().push_back(v);
        for (const auto& e : rgraph[v]) rdfs(e.to, curid);
    }

public:
    // id[v] = 頂点vはgroups[id[v]]に属する
    std::vector<int> id;
    std::vector<std::vector<int>> groups;

    explicit StronglyConnectedComponents(const Graph<Cost>& g)
        : graph(g), visited(graph.size, false), id(graph.size, -1) {
        revinit();

        for (int v = 0; v < graph.size; ++v) dfs(v);
        std::reverse(order.begin(), order.end());

        int curid = 0;
        for (int v : order) {
            if (id[v] < 0) {
                groups.push_back({});
                rdfs(v, curid);
                ++curid;
            }
        }
    }
};

template <class Cost>
Cost min_cost_arborescence(Graph<Cost> graph, int root) {
    std::vector<Edge<Cost>> rev(graph.size);

    for (int v = 0; v < graph.size; ++v) {
        for (const auto& e : graph[v]) {
            if (e.to == root || e.to == v) continue;
            if (rev[e.to].from < 0 || e.cost < rev[e.to].cost) {
                rev[e.to] = e;
            }
        }
    }

    Graph<Cost> lgraph(graph.size);
    Cost sum = 0;
    for (int v = 0; v < graph.size; ++v) {
        if (rev[v].from < 0) continue;
        lgraph.span(rev[v].from, rev[v].to, rev[v].cost);
        sum += rev[v].cost;
    }

    StronglyConnectedComponents<int> scc(lgraph);
    if (scc.groups.size() == graph.size) return sum;

    Graph<Cost> ngraph(scc.groups.size());
    Cost lcost = 0;

    for (int v = 0; v < graph.size; ++v) {
        if (graph[v].empty()) continue;

        if (scc.groups[scc.id[v]].size() == 1) {
            for (const auto& e : graph[v]) {
                if (scc.groups[scc.id[e.to]].size() == 1) {
                    ngraph.span(scc.id[v], scc.id[e.to], e.cost);  // そのまま追加
                } else {
                    ngraph.span(scc.id[v], scc.id[e.to], e.cost - rev[e.to].cost);
                }
            }
        } else {
            lcost += rev[v].cost;

            for (const auto& e : graph[v]) {
                if (scc.groups[scc.id[e.to]].size() == 1) {
                    ngraph.span(scc.id[v], scc.id[e.to], e.cost);
                } else {
                    ngraph.span(scc.id[v], scc.id[e.to], e.cost - rev[e.to].cost);
                }
            }
        }
    }

    return min_cost_arborescence(ngraph, scc.id[root]) + lcost;
}


int main() {
    int N, M, root;
    std::cin >> N >> M >> root;
    Graph<int> graph(N);
    for (int i = 0; i < M; ++i) {
        int from, to, cost;
        std::cin >> from >> to >> cost;
        graph.span(from, to, cost);
    }

    std::cout << min_cost_arborescence(graph, root) << std::endl;
    return 0;
}

