えびちゃんは有向グラフが大好きです。そんなえびちゃんの目の前に、N 頂点 M 辺の有向グラフが降ってきました。このグラフの頂点はそれぞれ 1 から N、辺はそれぞれ 1 から M で番号付けられています。そして、辺 i は頂点 u_i から v_i への向きに距離 d_i だけ伸びています。
えびちゃんは、このグラフのある2頂点 s と t について、 いくつかの辺に対して伸ばす操作を行い s-t 間の最短距離を伸ばしたいと考えました。すなわち、s-t 間の最短距離が、操作前のグラフでよりも、操作後のグラフでの方が長くなるようにしたいです。
すべて辺をわずかでも伸ばしてしまえば目的を達成できますが、えびちゃんはそれでは面白くないと考え、操作のルールを以下のように定めました。
このとき、えびちゃんが 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 の向きへたどることができる。
s から t への最短距離を伸ばすために必要な最小コストを 1 行に出力せよ。
3 3 1 3 1 2 1 1 2 3 1 1 1 3 1 1
1
辺 3 を距離 1 だけ伸ばせばよい。
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
8