0708 - 眠れる獅子の肝試し

時間制限 1 秒 / メモリ制限 256 MB / 得点 5 / Writer ei1503 / x 21 / 統計 /


TLE
1sec
MLE
256MB
得点
5

眠れる獅子の肝試し

眠れる獅子は一人で肝試しがしたい。
今、夢の中にいる彼の目の前には真夜中の森が広がっている。 森の中には休憩所がN個とそれらを結ぶ道がM本あり、彼はこの休憩所を経由しながら休憩所1から休憩所Nに向かい、また休憩所1に戻ってくる。休憩所siと休憩所tiを結ぶ道を通過すると彼の心拍数がxi上昇する。彼は心拍数がXを上回るとそのまま目を覚ますことはなくなり、無事に肝試しを終えた場合のみ新しい朝が訪れる。あなたは彼を導き、夢の世界から助け出しなさい。
※なお、休憩所1から休憩所Nまでの経路が存在しない場合も肝試し失敗である。

制約

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

  • 2 ≦ N ≦ 106
  • 1 ≦ M ≦ 106
  • 1 ≦ X ≦ 102
  • 1 ≦ xi ≦ 101
  • 1 ≦ si != ti ≦ N

入力

N M X
s1 t1 x1
s2 t2 x2
:
sm tm xm

出力

彼が無事起きることができたら起床時の心拍数、二度と目が覚めないのなら"sleep"を1行に出力しなさい。

入力例1

3 3 10
1 2 3
2 3 3
1 3 5

出力例1

10

入力例2

3 3 10
1 2 5
2 3 6
1 3 10

出力例2

sleep