0869 - 通行(通れるとは言っていない)

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1620 / x 13 / 統計 /


TLE
1sec
MLE
64MB
得点
1

問題

ある日、あなたは小数が使えなくされたのをなんとかするために、空にゲームを挑んだのだった・・・

空「ルールは簡単だ。まず n 個のチェックポイントと、それらを繋ぐ m 本の道、その道を通るためにかかる通行料 c 等の情報が与えられる。互いのプレイヤーはその情報をもとに、与えられた所持金 k を使い目的地に向かう。そして最終的な残金が多い方が勝者となる。もし目的地に辿り着けなければその時点で負けが確定する。」
白「にぃ。スタート、と、目的地の、場所は?」
空「そうだな・・・。スタートはチェックポイント 1 、目的地はチェックポイント n だ。ああそうだ、道はどちらの方向にも進むことができるものとしよう。」
空「じゃあルール説明もすんだし、ゲームを始めようか。」



「さあ、かかって来いよ・・・」

入力

n m k
a0 b0 c0
 : 
 : 
 : 
am-1 bm-1 cm-1

1 行目にチェックポイントの数を表す整数 n と、道の数を表す整数 m 、所持金を表す整数 k が与えられる。

2 行目以降につながっているチェックポイントを表す整数 ab と、そこの道の通行料を表す整数 c が与えられる

出力

最も残金が多い場合の最終的な所持金を出力せよ。もし、ゴールできない場合は"Oh..."と出力せよ。出力の最後に改行を入れることを忘れずに。

制約

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

  • 2 ≦ n ≦ 10000
  • 0 ≦ m ≦ min(n(n-1)/2,10000)
  • 1 ≦ k ≦ 1000
  • 1 ≦ a, bn
  • 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...