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;
#define MAX 101
#define INFTY 10001

class Edge {
public:
    int source, target, cost;
    Edge(int source = 0,int target = 0,int cost = 0): source(source), target(target), cost(cost) {}
    bool operator < (const Edge &e) const {
        return cost < e.cost;
    }
};
bool visited[MAX], comp[MAX]; //restore cycle groups
int group[MAX];

int solve(std::vector<Edge> &G, int V, int r) {

    std::vector<Edge> mins(V, Edge(-1, -1, INFTY)); //minimum edges

    //target specified min search
    for (unsigned long i = 0; i < G.size(); i++) {
        const Edge &e = G[i];
        mins[e.target] = std::min(mins[e.target], e);
    }
    mins[r] = Edge(-1, r, 0);

    for (int i = 0; i < V; i++) {
        group[i] = 0;
        visited[i] = comp[i] = false;
    }

    int cnt = 0;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            int node = i;
            std::vector<int> path;
            while (node != -1 && !visited[node]) {
                visited[node] = true;
                path.push_back(node);
                node = mins[node].source;
            }

            bool isCycle = false;
            for (unsigned long i = 0; i < path.size(); i++) {
                int current = path[i];
                group[current] = cnt;
                if (current == node)
                    comp[cnt] = isCycle = true;
                if (!isCycle)
                    cnt++;
            }

            if (isCycle)
                cnt++;
        }
    }

    if (cnt == V) {
        int ans = 0;
        for(unsigned long i = 0;i < mins.size(); i++) {
            Edge &e = mins[i];
            ans += e.cost;
        }
        return ans;
    }

    int ans = 0;
    for (unsigned long i = 0; i < mins.size(); i++) {
        Edge &e = mins[i];
        if (comp[group[e.target]])
            ans += e.cost;
    }

    std::vector<Edge> G2;
    for (unsigned long i = 0; i < G.size(); i++) {
        const Edge &e = G[i];
        int source = group[e.source], target = group[e.target], cost = e.cost;
        if (source == target)
            continue;
        else
            G2.push_back(Edge(source, target, cost - (comp[target] ? mins[e.target].cost : 0)));
    }
    return ans + solve(G2, cnt, group[r]);
}

int main() {

    std::vector<Edge> G;
    int V, E, r, source, target, cost;
    std::scanf("%d %d %d", &V, &E, &r);
    for(int i = 0; i< E; i++) {
        std::scanf("%d %d %d", &source, &target, &cost);
        G.push_back(Edge(source, target, cost));
    }
    std::printf("%d\n", solve(G, V, r));
    return 0;
}


