006 - パンケーキの出荷

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 3 /


TLE
1sec
MLE
64MB
得点
100

問題

このパンケーキは x Lの水を蓄えることができる。 x Lを超えると崩壊する。

パンケーキは部屋1で製造され部屋 n で出荷される。

部屋1と部屋 n の間には n-2 個の部屋と m 本の通路(部屋1と部屋 n がつながっていない場合もある)がある。

通路 i は部屋 ai と部屋 bi を双方向に結んでいる。

通路 i にはもともと ci Lの水があり時間が1たつと水が pi L増える。

どの通路も通過するのに時間が1かかる。 パンケーキは通った通路の水は全て蓄えてしまう。パンケーキに蓄えられた水は排出されない。

パンケーキに含まれる水の量をできるだけ少なくしたいため、パンケーキの蓄える水の量の最小を出力するプログラムを作成せよ。

パンケーキが崩壊した場合、または部屋1から部屋 n にたどり着けなかった場合は break と出力せよ。

最初時間は0から始まり、パンケーキは最初0Lの水を蓄えてるものとする。

入力

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

出力

部屋1から部屋nに行くまでに蓄える最小の水の量を出力する。

どうやってもパンケーキが崩壊、または部屋nまでたどり着けない場合は、"break"を出力する。

制約

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

  • 2 ≦ n ≦ 1000
  • 1 ≦ m ≦ min( n(n-1)/2 , 10000 )
  • 1 ≦ x ≦ 1000000
  • 1 ≦ c ≦ 100
  • 1 ≦ p ≦ 100

入出力例

入力例1

7 8 1000
1 2 3 2
1 3 4 1
2 4 2 1
3 5 3 2
3 6 8 3
4 6 5 1
5 6 4 2
6 7 1 2

出力例2

20

入力例2

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

出力例2

10

入力例3

4 3 100
1 2 2 3
2 3 3 1
3 1 4 3

出力例3

break