F： 最短距離を伸ばすえびちゃん (Ebi-chan Lengthens Shortest Paths)

問題

えびちゃんは有向グラフが大好きです。そんなえびちゃんの目の前に、N 頂点 M 辺の有向グラフが降ってきました。このグラフの頂点はそれぞれ 1 から N、辺はそれぞれ 1 から M で番号付けられています。そして、辺 i は頂点 u_i から v_i への向きに距離 d_i だけ伸びています。

えびちゃんは、このグラフのある2頂点 s と t について、 いくつかの辺に対して伸ばす操作を行い s-t 間の最短距離を伸ばしたいと考えました。すなわち、s-t 間の最短距離が、操作前のグラフでよりも、操作後のグラフでの方が長くなるようにしたいです。

すべて辺をわずかでも伸ばしてしまえば目的を達成できますが、えびちゃんはそれでは面白くないと考え、操作のルールを以下のように定めました。

• 各辺ごとに距離を伸ばしてよい（伸ばさない辺があってもよい）。
• 伸ばす距離は正の整数から任意に選択できる。
• 辺 i は距離 1 伸ばすごとに c_i のコストがかかる。

このとき、えびちゃんが s-t 間の最短距離を1以上伸ばすために必要な最小コストを求めてください。

入力形式

入力はすべて整数で与えられる。

N M s t
u_1 v_1 d_1 c_1
$\vdots$
u_M v_M d_M c_M

1 行目には、頂点数 N と辺数 M および、始点となる頂点と終点となる頂点の番号 s, t が空白区切りで与えられる。

1 + i 行目 (1 \leq i \leq M) には、 i 本目の辺の情報として、端点 u_i, v_i と距離 d_i および基礎コスト c_i が空白区切りで与えられる。ここで、i 本目の辺は頂点 u_i から v_i の向きへたどることができる。

制約

• 2 \leq N \leq 200
• 1 \leq M \leq 2,000
• 1 \leq s, t \leq N, s \neq t
• 1 \leq u_i, v_i \leq N, u_i \neq v_i (1 \leq i \leq M)
• 各 i, j (1 \leq i < j \leq M) について u_i \neq u_j または v_i \neq v_j が成り立つ
• 1 \leq d_i \leq 10 (1 \leq i \leq M)
• 1 \leq c_i \leq 10 (1 \leq i \leq M)
• s から t への経路が必ず存在する。

出力形式

s から t への最短距離を伸ばすために必要な最小コストを 1 行に出力せよ。

入力例1

3 3 1 3
1 2 1 1
2 3 1 1
1 3 1 1

出力例1

1

辺 3 を距離 1 だけ伸ばせばよい。

入力例2

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

出力例2

8

Note

Link

 

---