問題
忍 「アリス〜」
アリス「なぁに、シノ？」
忍 「クッキーを焼いたのでみんなにお裾分けしに行きましょう！」
アリス「それはGood Ideaだね！シノ！」
忍 「でも、みんなの家は私の家から少し離れているので、歩いていくのは疲れてしまいます……」
アリス「そーだ！シノ、シノの家からみんなの家を回って帰ってくるまでの最短経路を探そう！」
忍 「それは素晴らしいアイディアです。では、ここに地図があります。これを使って探しましょう」
アリス「よぉ〜し、シノが疲れないように私頑張るよ！」
入力
N M S a0 b0 c0 a1 b1 c1 ... ... ai bi ci ... aM bM cM
1行目には家の総数N,道の総数M,忍の家の番号Sが空白区切りで与えられる。
ここで、家の総数Nには忍の家も含まれることに注意せよ。また、N個の家にはそれぞれ1からNまでの番号が割り振られている。
続くM行には2つの家の番号ai,biとその家間の距離ciが与えられる。
2つの家間は双方から同じ距離で行き来でき、必ずすべての家に行ける経路があると考えて良い。また、道が重複することはない。
出力
忍の家からすべての家を回って帰ってくるまでの最短経路を出力せよ。
制約
すべての入出力ケースについて以下を満たす。
- 2 ≦ N ≦ 10
- 1 ≦ M ≦ 45
- 1 ≦ S,ai,bi ≦ N
- 1 ≦ ci ≦ 100
入出力例
入力例1
4 6 1 1 2 5 2 3 2 2 4 2 1 3 2 4 3 3 1 4 10
出力例1
11
解説
最初に忍の家1から家3へ行く。次に家3から家2へ行き、家4を訪れる。その後家4から家3を通って忍の家1へ戻ると最短経路になるので、11を出力する。
入力例2
2 1 1 1 2 10
出力例2
20