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
# AOJ GRL_2_B
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B

import sys
from heapq import heappush, heappop

V, E, r = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for _ in range(0, E)]

def solve(V, Edge, r):
    if V <= 1:
        return 0
    q = [[] for _ in range(0, V)]
    for s, t, w in Edge:
        heappush(q[t], (w, s))
    M = [(0, -1) for _ in range(0, V)]
    for t in range(0, V):
        if t != r:
            w, s = heappop(q[t])
            M[t] = (w, s)
    
    used = [False for _ in range(0, V)]
    hist = []
    cycle = []
    for t in range(0, V):
        w, s = M[t]
        if s == -1 or used[t] == True:
            continue
        if used[t] == False:
            used[t] = True
            hist += [t]
            tt = s
            while used[tt] == False:
                used[tt] = True
                hist += [tt]
                w, s = M[tt]
                if s == -1:
                    hist = []
                    break
                tt = s
            if used[tt] == True and s != -1 and 0 < len(hist):
                try:
                    k = hist.index(tt)
                    cycle = hist[k:]
                except:
                    continue
                finally:
                    pass
                break
                
    if len(cycle) == 0:
        return sum(m[0] for m in M)

    parent = min(cycle)
    rn = [0 for _ in range(0, V)]
    k = 0
    for t in range(0, V):
        if k == parent:
            k += 1
        if t in cycle:
            rn[t] = parent
        else:
            rn[t] = k
            k += 1
            
    Vp = V - len(cycle) + 1
    Ep = []
    for s, t, w in Edge:
        if s in cycle:
            if t in cycle:
                continue
            else:
                Ep += [[parent, rn[t], w]]
        else:
            if t in cycle:
                Ep += [[rn[s], parent, w - M[t][0]]]
            else:
                Ep += [[rn[s], rn[t], w]]
    r = rn[r]
    return solve(Vp, Ep, r) + sum(M[t][0] for t in cycle)

print(solve(V, Edge, r))

