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 <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>

//#include <bits/stdc++.h>
using namespace std;
using LL = int;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourd; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, q, last, cnt, sum, ans, d[1 << 20], a[2000000][3], b[2000000];
string str, ss;
bool f[1100][1100];
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
struct Edge { LL to, cost; };
vector<Edge>vec[200000];
vector<LL>v;
map<Pll, LL>ma;
set<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
LL Chu_Liu_Edmonds(vector<vector<Edge>> edges, int V, int start) { //Vは頂点数,startは根の頂点
	vector<Pll> mins(V, Pll(INF, -1));	// その頂点に入る最小辺の(辺コスト, 始点)
	rep(i, V) {
		rep(j, edges[i].size()) {
			Edge edge = edges[i][j];
			mins[edge.to] = min(mins[edge.to], Pll(edge.cost, i));
		}
	}
	mins[start] = Pll(-1, -1);	// 始点には辺が入らない

	vector<LL> group(V, 0);
	vector<bool> isCycle(V, false);	// 頂点が縮約されたもの（元閉路）かどうか
	int count = 0;	// グループ分けで割り振る番号＝縮約後の頂点数

	vector<bool> used(V, false);
	rep(i, V) {
		if (used[i])continue;
		vector<LL> chain;
		int cursor = i;
		while (cursor != -1 && !used[cursor]) {
			// 頂点iから元を辿っていく
			used[cursor] = true;
			chain.push_back(cursor);
			cursor = mins[cursor].second;	// 頂点cursorに入ってくる位置へ移動
		}
		if (cursor != -1) {
			// 閉路発見の可能性あり
			// chainの現cursor以降が閉路
			bool inCycle = false;	// 閉路に突入したかどうかを表すフラグ
			rep(j, chain.size()) {
				group[chain[j]] = count;
				if (chain[j] == cursor) {
					// ここから閉路
					isCycle[count] = true;
					inCycle = true;
				}
				if (!inCycle)count++;	// 閉路内でなければ別グループ扱い
			}
			if (inCycle)count++;
		}
		else {
			// 根で終了した＝閉路見つからず
			// chain内の頂点すべてを単独のグループに分ける
			rep(j, chain.size()) {
				group[chain[j]] = count;
				count++;
			}
		}
	}
	// この時点でグループ分けが終了している

	if (count == V) {
		// 縮約で頂点数が不変＝閉路が無い
		LL ans = 1;	// 根のコスト-1を打ち消すための1
		rep(i, V) {
			ans += mins[i].first;
		}
		return ans;
	}

	// 縮約した閉路のコスト合計を計算
    LL res = 0;
	rep(i, V) {
		if (i != start && isCycle[group[i]]) {
			res += mins[i].first;
		}
	}

	// 閉路が存在するので、新たにグラフを構成
	vector<vector<Edge>> newEdges;
	newEdges.resize(count);
	rep(i, V) {
		rep(j, edges[i].size()) {
			Edge edge = edges[i][j];
			int to = edge.to;
			int gfrom = group[i];
			int gto = group[edge.to];
			if (gfrom == gto) {
				// 始点と終点が同じグループ（同じ閉路）なら、追加せず
				continue;
			}
			else if (isCycle[gto]) {
				// 終点が縮約後の閉路なら、コストを計算し直して追加
				newEdges[gfrom].push_back(Edge{ gto,edge.cost - mins[to].first  });
			}
			else {
				// それ以外は、単純に追加
				newEdges[gfrom].push_back(Edge{ gto,edge.cost });
			}
		}
	}

	return res + Chu_Liu_Edmonds(newEdges, count, group[start]);
}

int main() {
	LL V, E, r;
	cin >> V >> E >> r;
	vector<vector<Edge>> es;
	es.resize(V);
	rep(i, E) {
		LL s, t, w;
		cin >> s >> t >> w;
		es[s].push_back(Edge{ t,w });
	}

	cout << Chu_Liu_Edmonds(es, V, r) << endl;

	return 0;
}
