006 - ブラジルと太陽

時間制限 1 秒 / メモリ制限 256 MB / 得点 60 / x 6 /


TLE
1sec
MLE
256MB
得点
60

問題

ここは試練の間である。


ブラジルは太陽と共に生きている。


人々は死ぬ。


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

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

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

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

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

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

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

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

入力

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

出力

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

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

制約

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

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

入出力例

入力例1

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

出力例1

10

入力例2

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

出力例2

You were dead.

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