問題
ある日、あなたは小数が使えなくされたのをなんとかするために、空にゲームを挑んだのだった・・・
空「ルールは簡単だ。まず n 個のチェックポイントと、それらを繋ぐ m 本の道、その道を通るためにかかる通行料 c 等の情報が与えられる。互いのプレイヤーはその情報をもとに、与えられた所持金 k を使い目的地に向かう。そして最終的な残金が多い方が勝者となる。もし目的地に辿り着けなければその時点で負けが確定する。」
白「にぃ。スタート、と、目的地の、場所は？」
空「そうだな・・・。スタートはチェックポイント 1 、目的地はチェックポイント n だ。ああそうだ、道はどちらの方向にも進むことができるものとしよう。」
空「じゃあルール説明もすんだし、ゲームを始めようか。」
「さあ、かかって来いよ・・・」
入力
n m k a0 b0 c0 : : : am-1 bm-1 cm-1
1 行目にチェックポイントの数を表す整数 n と、道の数を表す整数 m 、所持金を表す整数 k が与えられる。
2 行目以降につながっているチェックポイントを表す整数 a 、 b と、そこの道の通行料を表す整数 c が与えられる
出力
最も残金が多い場合の最終的な所持金を出力せよ。もし、ゴールできない場合は"Oh..."と出力せよ。出力の最後に改行を入れることを忘れずに。
制約
全ての入出力ケースについて以下を満たす。
- 2 ≦ n ≦ 10000
- 0 ≦ m ≦ min(n(n-1)/2,10000)
- 1 ≦ k ≦ 1000
- 1 ≦ a, b ≦ n
- 0 ≦ c ≦ 1000
入出力例
入力例1
2 1 10 1 2 5
出力例1
5
入力例2
10 4 10 1 2 5 2 5 5 5 10 5 1 10 100
出力例2
Oh...