002 - 神綺ママはアリスちゃんに会いたい!

注意

問題読みたくない人は、問題概要まで読み飛ばしてくださいm(_ _)m

問題

アリス・マーガトロイドの住む魔法の森。

そこに魔界の神、神綺とそのメイドの夢子が幻想郷のお仕事のついでにアリスの家に遊びに行こうとしていた。

神綺：「夢子ちゃん♪アリスちゃんに会うの楽しみね〜」

夢子：「そうですね。アリスの家の場所は先ほど確認いたしましたので、ご案内いたします」

神綺：「うん♪夢子ちゃん、道案内よろしくね〜」

しかし、魔法の森を進む途中で結界にはばまれて、２人はこれ以上進めなくなってしまった。

結界の手前には n 個のオブジェが置いてあり、全てのオブジェに埋め込まれたオーブはからっぽになっていた。

オブジェのうちの１つ s は、手形のような形をしており、魔力が流し込めるようになっていた。

神綺：「困ったわ、これじゃあ夢子ちゃん特製のアップルパイが冷めちゃうわ〜」

夢子：「申し訳ありません。私が不甲斐ないばっかりに・・・」

神綺：「あら、大丈夫よ。夢子ちゃんのせいじゃないわ。それにどうやらこの仕掛けを動かせば結界は解けそうよ」

夢子：「・・・といいますと？」

神綺：「この全てのオブジェのオーブに魔力を注げばいいのよ。手形のオブジェから魔力を流し込めるわ。

　　　　それに、目には見えない魔力の通り道が m 本あって、オブジェとオブジェを繋いでいるようね。

　　　　魔力の通り道を通じて魔力をオブジェに送れば、そのオブジェから他のオブジェにも通り道を通じて魔力を送れるようになるわ。

　　　　でも、魔力の通り道 i にはコスト c_i があって、コストが大きいほど、魔力を送りづらくなってしまうの。

　　　　ねぇ夢子ちゃん、魔力の通り道とそのコストを教えてあげるから、全てのオブジェに魔力を注ぐために必要な

　　　　最小コストを考えてくれないかしら？」

夢子：「わかりました。必ずや神綺様のご期待に応えて見せます」

神綺：「本当は私、魔界神だからこれくらいの魔力の消費量なんか考えなくてもいいんだけどね♪」

問題概要

オブジェの数n、オブジェを相互に結ぶ魔力の通り道の数m、魔力の通り道iを通過するときにかかるコストc_i、

スタート地点sが与えられるため、全てのオブジェを繋ぐネットワークを構成するために必要な最小コストを求めよ。

入力

一行目にオブジェの数n、魔力の通り道の数m、手形のオブジェの位置sが与えられる。

続くm行に魔力の通り道iの情報が与えられる。

通り道iは、オブジェa_iとオブジェb_iを相互に結び、魔力を流すのにc_iのコストがかかる。

n m s
a1 b1 c1
   ・
   ・
   ・
am bm cm

出力

全てのオブジェを繋ぐネットワークを構成するために必要な最小コストを出力せよ。最後に改行すること。

制約

全ての入力ケースについて以下を満たす。

• 2 ≦ n ≦ 10⁵
• n-1 ≦ m ≦ min(10⁶、n(n-1)/2)
• 1 ≦ a,b,s ≦ n
• 1 ≦ c ≦ 100

---

入出力例

入力例1

4 5 3
1 2 3
1 3 5
2 3 1
2 4 4
3 4 2

出力例1

6

解説

上の図のように赤線で繋ぐのが最小コストである。

入力例2

13 23 3
1 2 3
1 3 2
1 4 5
2 4 1
2 7 6
3 4 2
3 5 2
4 5 4
4 6 7
5 8 9
5 9 8
6 7 1
6 8 4
7 8 8
7 10 8
8 9 2
8 10 8
8 11 4
9 12 5
10 13 4
11 12 3
11 13 1
12 13 5

出力例2

32

作者コメント

神アリは親子！親子です