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
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Map;

import java.util.Scanner;

public class Main {
	
	// root ????????????????°???¨?????¨????????????????±???????
	public static long Chu_Liu_Edmonds(final int V, int root, ArrayList<Map<Integer, Long>> rev_adj) {
		// ??????????????\???????°???????????????????????±???????
		long[] min_costs = new long[V];
		int[] min_pars = new int[V];
		min_costs[root] = 0;
		min_pars[root] = root;

		for (int start = 0; start < V; start++) {
			if (start == root) { continue; }
			long min_cost = -1;
			int min_par = -1;

			for (final Map.Entry<Integer, Long> entry : rev_adj.get(start).entrySet()) {
				final int par = entry.getKey();
				final long cost = entry.getValue();

				if (min_cost < 0 || min_cost > cost) {
					min_par = par;
					min_cost = cost;
				}
			}

			min_pars[start] = min_par;
			min_costs[start] = min_cost;
		}

		// ????????? 1 ???????????????
		boolean has_cycle = false;
		int[] belongs = new int[V];
		for(int i = 0; i < V; i++){ belongs[i] = i; }

		boolean[] is_cycle = new boolean[V];

		for (int start = 0; start < V; start++) {
			if(min_pars[start] < 0){ continue; }

			boolean[] used = new boolean[V];
			int curr = start;
			while (!used[curr] && min_pars[curr] != curr) {
				used[curr] = true;
				curr = min_pars[curr];
			}

			// ??????????????\?????????
			if (curr != root) {
				belongs[curr] = V;
				is_cycle[curr] = true;

				int cycle_start = curr;
				while (min_pars[curr] != cycle_start) {
					belongs[min_pars[curr]] = V;
					is_cycle[min_pars[curr]] = true;
					curr = min_pars[curr];
				}

				has_cycle = true;

				break;
			}else{
				// ????????¨??¢?????????
			}
		}

		if(!has_cycle){
			long sum = 0;
			for(int i = 0; i < V; i++){
				sum += Math.max(0, min_costs[i]);
			}

			return sum;
		}


		long cycle_sum = 0;
		for(int i = 0; i < V; i++){
			if(!is_cycle[i]){ continue; }
			cycle_sum += min_costs[i];
		}

		ArrayList<Map<Integer, Long>> next_rev_adj = new ArrayList<Map<Integer, Long>>();
		for(int i = 0; i <= V; i++){
			next_rev_adj.add(new HashMap<Integer, Long>());
		}
		for(int start = 0; start < V; start++){
			final int start_belongs = belongs[start];
			for(final Entry<Integer, Long> entry : rev_adj.get(start).entrySet()){
				final int prev = entry.getKey();
				final int prev_belongs = belongs[prev];


				if(start_belongs == prev_belongs){ continue; }
				else if(is_cycle[start]){
					if(!next_rev_adj.get(start_belongs).containsKey(prev_belongs)){
						next_rev_adj.get(start_belongs).put(prev_belongs, rev_adj.get(start).get(prev) - min_costs[start]);
					}else{
						final long old_cost = next_rev_adj.get(start_belongs).get(prev_belongs);
						next_rev_adj.get(start_belongs).put(prev_belongs, Math.min(old_cost, rev_adj.get(start).get(prev) - min_costs[start]));
					}
				}else{
					if(!next_rev_adj.get(start_belongs).containsKey(prev_belongs)){
						next_rev_adj.get(start_belongs).put(prev_belongs, rev_adj.get(start).get(prev));
					}else{
						final long old_cost = next_rev_adj.get(start_belongs).get(prev_belongs);
						next_rev_adj.get(start_belongs).put(prev_belongs, Math.min(old_cost, rev_adj.get(start).get(prev)));
					}
				}
			}
		}

		return cycle_sum + Chu_Liu_Edmonds(V + 1, root, next_rev_adj);
	}
		
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		final int V = sc.nextInt();
		final int E = sc.nextInt();
		final int S = sc.nextInt();		
		
		ArrayList<Map<Integer, Long>> fwd_adj = new ArrayList<Map<Integer, Long>>();
		ArrayList<Map<Integer, Long>> rev_adj = new ArrayList<Map<Integer, Long>>();
		for (int i = 0; i < V; i++) {
			fwd_adj.add(new HashMap<Integer, Long>());
		}
		for (int i = 0; i < V; i++) {
			rev_adj.add(new HashMap<Integer, Long>());
		}
		
		for (int i = 0; i < E; i++) {
			final int s = sc.nextInt();
			final int t = sc.nextInt();
			final long w = sc.nextLong();

			if (!fwd_adj.get(s).containsKey(t)) {
				fwd_adj.get(s).put(t, w);
			} else {
				fwd_adj.get(s).put(t, Math.min(w, fwd_adj.get(s).get(t)));
			}

			if (!rev_adj.get(t).containsKey(s)) {
				rev_adj.get(t).put(s, w);
			} else {
				rev_adj.get(t).put(s, Math.min(w, rev_adj.get(t).get(s)));
			}
		}

		System.out.println(Chu_Liu_Edmonds(V, S, rev_adj));
	}
}