最小全域有向木

重み付き有向グラフG(V, E) について、頂点rを根とする最小全域有向木の辺の重みの総和を求めて下さい。

入力

|V| |E| r
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1

|V|, |E|はそれぞれグラフGの頂点の数と辺の数を示す。グラフGの頂点にはそれぞれ0, 1, ..., |V|-1 の番号が付けられている。rは最小全域有向木の根を示す。

s_i, t_i はグラフGのi番目の辺をこの順で結ぶ２つの頂点である（有向）。w_i は i 番目の辺の重みである。

出力

最小全域有向木の辺の重みの総和を１行に出力する。

制約

• 1 ≤ |V| ≤ 100
• 0 ≤ |E| ≤ 1,000
• 0 ≤ w_i ≤ 10,000
• グラフGはrを根とする有向木をもつ

入力例 1

4 6 0
0 1 3
0 2 2
2 0 1
2 3 1
3 0 1
3 1 5

出力例 1

6

入力例 2

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

出力例 2

11

---