006 - ブラジルと太陽

問題

人々は死にたくないのでブラジルからの脱出を試みた。ブラジルには n 個の地点がある。

人々は地点1に存在し、ブラジルの出口は地点 n に存在する。

地点1から地点 n までは m 本の道でつながっている。 道 i は、地点 a_i と b_i を双方につないでいる。

地点1から地点 n まで行く道は必ず存在する。

m 本の道には決まった量の日光が降り注ぐ。 i 本目の道に降り注ぐ日光の量を c_i とする。

人々は降り注ぐ日光を x まで耐えられる。 x を超えると人々は死ぬ。日光は体に悪いので人々はできるだけ日光を浴びたくない。

人々がブラジルか脱出できるかを判断し、脱出できる場合は脱出までに浴びる最小の日光を出力

脱出できない場合は"You were dead."と出力するプログラムを作成せよ。

入力

n m x
a1 b1 c1
   ・
   ・
   ・
am bm cm

出力

人々がブラジルを脱出するまでに浴びる最小の日光を出力せよ。

なお、どうやっても人々が力尽きてしまう場合は、"You were dead."を出力せよ。

制約

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

• 2 ≦ n ≦ 10⁶
• 1 ≦ m ≦ min( n(n-1)/2 , 10⁶ )
• 1 ≦ x ≦ 200
• 1 ≦ c ≦ 20

入出力例

入力例１

4 5 10
1 2 3
2 3 5
1 3 5
2 4 7
3 4 6

出力例１

10

入力例２

4 4 10
1 2 20
1 3 20
2 4 20
3 4 20

出力例２

You were dead.

人々はどうあがいても死ぬ。