Water Pipe Construction

Time Limit : 8 sec, Memory Limit : 65536 KB

Water Pipe Construction

21XX 年,ついに人類は火星への移住計画を開始させた.火星への移住第一陣に選抜されたあなたは,火星行政中央局(the Administrative Center of Mars)に配属され,火星で起こる様々な問題に対処している.行政中央局の目下の最大の問題は自立した需要供給サイクルの確保である.月からの援助物資が届くまでには数ヶ月単位の時間がかかるため,基本的には火星内の需要は火星内で解決する必要がある.それに加えて,循環システムを確立するまでは資源を極力節約することが求められる.

行政中央局は極地にある氷の採掘を開始した.太陽光でこれを溶かし,水として個々の基地に供給することが最終目標である.最初の段階として,水源のある基地から2つの主要基地までの導水管を敷設することにした.また,現時点ではいくつかの基地とそれらを結ぶ道路以外には開拓されておらず,未開拓のところに導水管を敷設するには多大なるコストと燃料を要するため,道路に沿って導水管を敷設することにした.さらに,技術上の制約のため,彼らの導水管は常に一方向だけに水が流れる.

あなたの仕事は,これらの条件のもとで,導水管の敷設にかかるコストを最小にするプログラムを作成することである.

Input

入力は複数のデータセットから構成される.

データセットの最初の行は 5 つの整数からなる.これらは順に,火星に存在する基地の数 n (3 <= n <= 100),基地を結ぶ道路の数 m (2 <= m <= 1000),水源となる基地の番号 s, 導水管の目的地となる 2 つの主要基地の番号 g1g2 を表す.基地の番号は 1 から n までの整数で表される.sg1g2 は互いに異なる.

続く m 行には,導水管を敷設可能な道路の情報が与えられる.各行はある 2 つの基地間における道路の情報を表しており,3 つの整数 b1b2c (1 <= c <= 1000) からなる.ここに b1b2 は道路の始端および終端の基地の番号を表し,これらは互いに異なる.c は基地 b1 から基地 b2 に向かう導水管を敷設するためにかかるコストである.

全てのデータセットについて,水源から目的地まで水を供給する経路は常に存在すると仮定してよい.また,ある 2 つの基地間には高々 1 つの道路しか存在しないことから,コストの情報はそれぞれの方向について高々 1 回しか与えられない.

入力の終了はスペース文字で区切られた 5 つのゼロが含まれる行で表される.

Output

それぞれのデータセットに対して,導水管を敷設するコストの最小値を 1 行に出力せよ.

Sample Input

4 5 1 3 4
1 2 5
2 3 5
2 4 5
1 3 8
1 4 8
0 0 0 0 0

Output for the Sample Input

15

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2006, 2006-06-18
http://acm-icpc.aitea.net/