006 - パンケーキの出荷

問題

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

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

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

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

通路 i にはもともと c_i Lの水があり時間が1たつと水が p_i 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