p02365 Minimum-Cost Arborescence
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
```python
from collections import defaultdict
from itertools import chain

nv, ne, r = map(int, input().split())

in_edges = defaultdict(set)
out_edges = defaultdict(set)
while ne:
    s, t, w = map(int, input().split())
    in_edges[t].add((w, s))
    out_edges[s].add((w, t))
    ne -= 1


def chu_liu_edmond(vertices, cycle_cost):
    global in_edges, out_edges, nv, r

    total_cost = cycle_cost
    prev_v = {v: None for v in vertices}
    next_vs = {v: set() for v in vertices}

    for t in vertices:
        if t == r:
            continue
        min_in_w, min_in_s = min(in_edges[t])
        total_cost += min_in_w
        prev_v[t] = min_in_s
        next_vs[min_in_s].add(t)

    visited = {r}
    queue = set(next_vs[r])
    while queue:
        t = queue.pop()
        visited.add(t)
        queue.update(next_vs[t])

    cycles = []
    for i in vertices:
        if i in visited:
            continue

        cycle_vertices = set()
        while i not in visited:
            visited.add(i)
            cycle_vertices.add(i)
            i = prev_v[i]

        # Branched single path from cycle
        if i not in cycle_vertices:
            continue

        # Current cycle_vertices are not necessarily cycle (may contain branch from cycle)
        cycle_vertices, j = {i}, prev_v[i]
        while j != i:
            cycle_vertices.add(j)
            j = prev_v[j]

        cycles.append(cycle_vertices)

    if not cycles:
        return total_cost

    for cycle in cycles:
        vertices.difference_update(cycle)
        vertices.add(nv)

        for v in cycle:
            prev_e_cost = min(in_edges[v])[0]
            cycle_cost += prev_e_cost
            for w, t in out_edges[v]:
                if t in vertices:
                    out_edges[nv].add((w, t))
                    in_edges[t].remove((w, v))
                    in_edges[t].add((w, nv))
            for w, s in in_edges[v]:
                if s in vertices:
                    new_w = w - prev_e_cost
                    in_edges[nv].add((new_w, s))
                    out_edges[s].remove((w, v))
                    out_edges[s].add((new_w, nv))
            del in_edges[v]
            del out_edges[v]

        nv += 1

    return chu_liu_edmond(vertices, cycle_cost)


print(chu_liu_edmond(set(range(nv)), 0))
```