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 <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN (-2147483647 - 1)
#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;

class GraphCLE {
private:
	struct node {
		ll d;
		int edgeid;
		set<int> inc;
		int mode;
	};
	vector<node> nodes;
	struct edgeinfo { int from, to, cost; };
	struct edge {
		vector<edgeinfo> info;
		int mode;
	};
	vector<edge> edges;
	int n;
	vector<set<int>> cycle;
	bool choose_min_edge(int start) {
		Loop(i, edges.size()) {
			edgeinfo buf = edges[i].info.back();
			if (buf.to != start && buf.cost < nodes[buf.to].d) {
				nodes[buf.to].d = buf.cost;
				nodes[buf.to].edgeid = i;
			}
		}
		Loop(i, n) {
			if (i == start) continue;
			if (nodes[i].d == INFLL) return false;
			edges[nodes[i].edgeid].mode = 1;
		}
		return true;
	}
	bool find_cycle() {
		Loop(i, nodes.size()) {
			if (nodes[i].mode == 1) nodes[i].mode = 0;
		}
		Loop(i, nodes.size()) {
			if (nodes[i].mode > 0) continue;
			stack<int> stk;
			int b = i;
			while (nodes[b].mode == 0) {
				stk.push(b);
				nodes[b].mode = -1;
				if (nodes[b].edgeid == -1) break;
				b = edges[nodes[b].edgeid].info.back().from;
			}
			if (nodes[b].edgeid != -1 && nodes[b].mode == -1) {
				cycle.push_back({ b });
				while (stk.top() != b) {
					cycle.back().insert(stk.top());
					nodes[stk.top()].mode = 1;
					stk.pop();
				}
			}
			while (stk.size()) {
				nodes[stk.top()].mode = 1;
				stk.pop();
			}
		}
		if (cycle.size()) return true;
		else return false;
	}
	bool contract() {
		while (cycle.size()) {
			set<int> pack = cycle.back(); cycle.pop_back();
			int newnodeid = nodes.size();
			nodes.push_back({ INFLL,-1,pack,0 });
			Loop(i, edges.size()) {
				edgeinfo buf = edges[i].info.back();
				if (pack.find(buf.from) != pack.end()) {
					if (pack.find(buf.to) != pack.end()) {
						if (edges[i].mode == 1) edges[i].mode = 2;
						else edges[i].mode = -1;
					}
					else edges[i].info.push_back({ newnodeid, buf.to, buf.cost });
				}
				else if (pack.find(buf.to) != pack.end()) {
					int x = buf.cost - edges[nodes[buf.to].edgeid].info.back().cost;
					edges[i].info.push_back({ buf.from, newnodeid, x });
					if (x < nodes.back().d) {
						nodes.back().d = x;
						nodes.back().edgeid = i;
					}
				}
			}
			if (nodes.back().edgeid == -1) return false;
			edges[nodes.back().edgeid].mode = 1;
			auto itr = nodes.back().inc.begin();
			while (itr != nodes.back().inc.end()) {
				nodes[*itr].mode = 2;
				itr++;
			}
		}
		return true;
	}
	void unfold() {
		while (nodes.size() > n) {
			while (edges[nodes.back().edgeid].info.back().to >= nodes.size() - 1) {
				edges[nodes.back().edgeid].info.pop_back();
			}
			int flag = edges[nodes.back().edgeid].info.back().to;
			auto itr = nodes.back().inc.begin();
			while (itr != nodes.back().inc.end()) {
				if (edges[nodes[*itr].edgeid].info.back().to == flag) {
					edges[nodes[*itr].edgeid].mode = -1;
					nodes[*itr].d = edges[nodes.back().edgeid].info.back().cost;
					nodes[*itr].edgeid = nodes.back().edgeid;
				}
				else edges[nodes[*itr].edgeid].mode = 1;
				itr++;
			}
			nodes.pop_back();
		}
		Loop(i, edges.size()) {
			if (edges[i].mode == 1) {
				nodes[edges[i].info[0].to].d = edges[i].info[0].cost;
				nodes[edges[i].info[0].to].edgeid = i;
			}
		}
	}
public:
	vll result;
	GraphCLE(vector<vector<P>> data) {
		n = data.size();
		result.resize(n);
		nodes.resize(n);
		Loop(i, n) {
			Loop(j, data[i].size()) {
				edgeinfo buf = { i, data[i][j].first, data[i][j].second };
				edges.push_back({ { buf } , 0 });
			}
		}
	}
	bool mainfunc(int start) {
		Loop(i, n) 	nodes[i] = { INFLL, -1,{}, 0 };
		nodes[start].d = 0;
		if (!choose_min_edge(start)) return false;
		while (find_cycle()) {
			if (!contract()) return false;
		}
		unfold();
		Loop(i, n) {
			result[i] = nodes[i].d;
		}
		return true;
	}
};

int main() {
	int n, m, r; cin >> n >> m >> r;
	vector<vector<P>> data(n);
	Loop(i, m) {
		int s, t, d; cin >> s >> t >> d;
		data[s].push_back({ t,d });
	}
	GraphCLE cle(data);
	if (cle.mainfunc(r)) {
		ll ans = 0;
		Loop(i, n) {
			ans += cle.result[i];
		}
		cout << ans << endl;
	}
	return 0;
}