問題
複数の島が橋でつながれた世界、「Shorib」。
別世界からのテロリストがこの世界のある島に「Homono virus(以下HV)」をばらまいた。
HVは徐々に島々を汚染していき、最後には汚染された島にいる者を全てホモに変えてしまう恐ろしいものだ。
あなたはこの世界の管理者である。そして今、あなたがいる島にHVがばらまかれた。
あなたはすぐに『汚染されることのない「Nonke」と呼ばれる聖域』へ行き、
「Rez virus(以下RV)」と呼ばれるアンチHVを所持した上で最も汚染された地域へ持って行かなければならない。
あなたはプログラミングの能力にも長けているので、島、島と島の距離、汚染度等のデータを元に、
できうる限り速く、そして自分ができうる限りホモにならないように計算してこの世界を救うしかない。
島と島の橋の移動には時間がかかる。
島の移動中は時間に含めない。何故なら全ての島には便利なテレポーターが設置されているからだ。
-汚染度の増え方について-
・あなたがいる島から汚染は始まる。汚染度は1分で1増える。・橋で繋がっている島の片方が汚染されていて、もう片方が汚染されていない場合
・新しく汚染されていない島が汚染を開始する。
・橋の材質上、HVは橋を汚染することはできないが、移動にはこの世界の人種と同じ時間がかかる。
・両方汚染されている場合
・汚染された島同士は干渉しない。1分たつと両方とも汚染度が1増える。
・あなたと汚染度の関係
・汚染された地域に足を踏み入れた場合、島の汚染度の分あなたのホモ度が上がる。
・島での滞在時間は考えないので、島iの汚染度がnだとすると、島iから島i+1に移動したときの島iの汚染度はnである。
・橋の移動中でHVに接触しても汚染度は増えない。何故ならHVは地形を汚染してから人に汚染するからである。
入力
N M S G a1 b1 c1 . . . . . . . . . am bm cm
1行目に左から、「島の数」、「橋の数」、「あなたが最初に居る島」、「聖域の島」が与えられる。
2行目からM+1行目に左から「橋がかかる島1」「橋がかかる島2」「その橋の移動時間」が与えられる。
すべての入力は空白区切りで与えられる。
出力
あなたの最終的なホモ度と最初の汚染された島（あなたが最初に居る島）から聖域の島までの最短経路を空白区切りで出力する。
どうあがいても聖域に着くことができない場合は"Homoed."と出力すること。
改行を忘れないこと。
制約
全ての入出力ケースで以下の条件を満たす。
- 3 ≦ N ≦ 800, 3 ≦ M ≦ 8000, 1 ≦ S ≦ N, 1 ≦ G ≦ N
- S ≠ Gは保証されている。
- 1 ≦ ai, bi ≦ N, 1 ≦ cm ≦ 100
- ai, biにおいて、同じ組み合わせが複数与えられることはない。(多分。仮にあっても影響はないと思うけど)
入出力例
入力例1
4 4 1 4 1 3 5 1 2 4 2 3 2 3 4 10
出力例1
50 15
入力例2
5 8 1 5 1 3 7 1 2 5 4 1 8 3 2 2 2 4 4 3 4 4 3 5 6 4 5 3
出力例2
28 11
入力例3
5 4 1 5 1 2 3 5 4 9 2 3 5 1 3 4
出力例3
Homoed.