003 - 眠れる獅子の肝試し

眠れる獅子の肝試し

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

制約

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

• 2 ≦ N ≦ 10⁶
• 1 ≦ M ≦ 10⁶
• 1 ≦ X ≦ 10²
• 1 ≦ x_i ≦ 10¹
• 1 ≦ s_i != t_i ≦ 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

出力例１

10

入力例2

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

出力例2

sleep