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;

constexpr int INF = numeric_limits<int>::max();

struct Edge{
    int from, to, cost;
    Edge(int f = 0, int t = 0, int c = 0): from(f), to(t), cost(c) {}
    bool operator<(const Edge & other){return this->cost < other.cost;}
};

struct Graph{
    int V, r;
    vector<Edge> edges;
    Graph(): V(0), r(0), edges(0){}
    Graph(int n_v, int root, vector<Edge> & _edges): V(n_v), r(root), edges(_edges){}
};

pair<vector<int>, vector<int>> select_parents(int V, int r, const vector<Edge> & edges){
    vector<int> parents(V, -1);
    vector<int> costs(V, INF);
    for (auto e : edges){
        if (parents[e.to] == -1 or e.cost < costs[e.to]){
            parents[e.to] = e.from;
            costs[e.to] = e.cost;
        }
    }
    parents[r] = r;
    return make_pair(parents, costs);
}

void track_back(int v, int r, vector<int> & groups, vector<bool> & visited, const vector<int> & parents){
    vector<int> hist;
    for (; not visited[v]; visited[v] = true, hist.push_back(v), v = parents[v]);
    if (groups[v] == -1) {  // v is the start of a cycle (loop).
        groups[v] = v;
        while (not hist.empty() and hist.back() != v){
            groups[hist.back()] = v;
            hist.pop_back();
        }
        if (not hist.empty()) hist.pop_back();  // remove v from the hist to avoid changing the groups[v].
        for (auto u : hist) groups[u] = r;      // the rest of the vertexes in hist do not form a cycle.
    }else{
        for (auto u : hist) groups[u] = r;
    }
}

vector<int> detect_cycles(int V, int r, const vector<int> & parents){
    vector<int> groups(V, -1);
    vector<bool> visited(V, false);
    groups[r] = r;
    visited[r] = true;
    for (int v = 0; v < V; ++v){
        if (not visited[v]) track_back(v, r, groups, visited, parents);
    }
    return groups;
}

int count_cycle_cost(int V, int r, const vector<int> & costs, const vector<int> & groups){
    int cycle_cost = 0;
    for (int v = 0; v < V; ++v){
        if (groups[v] != r) cycle_cost += costs[v];
    }
    return cycle_cost;
}

Graph compress_cycle(int V, int r, const vector<Edge> & edges, const vector<int> & costs, const vector<int> & groups){
    vector<int> new_label(V, -1);
    int label = 0;
    for (int v = 0; v < V; ++v){
        int g = groups[v];
        if (g == r){
            new_label[v] = label;
            ++label;
        }else if (new_label[g] == -1){
            new_label[g] = label;
            new_label[v] = label;
            ++label;
        }else{
            new_label[v] = new_label[g];
        }
    }
    Graph new_graph;
    for (auto & e : edges){
        if (groups[e.to] == r){
            new_graph.edges.emplace_back(new_label[e.from], new_label[e.to], e.cost);
        }else if (groups[e.from] != groups[e.to]){
            assert(e.cost >= costs[e.to]);
            new_graph.edges.emplace_back(new_label[e.from], new_label[e.to], e.cost - costs[e.to]);
        }
    }
    new_graph.V = *max_element(begin(new_label), end(new_label)) + 1;
    new_graph.r = new_label[r];
    return new_graph;
}

int minCostArborescence(int V, int r, const vector<Edge> & edges){
    auto result = select_parents(V, r, edges);
    auto parents = result.first;
    auto costs = result.second;
    auto groups = detect_cycles(V, r, parents);
    int cycle_cost = count_cycle_cost(V, r,costs, groups);
    if (cycle_cost == 0) {
        int cost = 0;
        for (int i = 0; i < V; ++i) if (i != r) cost += costs[i];
        return cost;
    }else{
        auto new_graph = compress_cycle(V, r, edges, costs, groups);
        return cycle_cost + minCostArborescence(new_graph.V, new_graph.r, new_graph.edges);
    }
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int V, E, r;
    cin >> V >> E >> r;
    vector<Edge> edges(E);
    for (auto & e : edges) cin >> e.from >> e.to >> e.cost;
    cout << minCostArborescence(V, r, edges) << endl;
    return 0;
}