問題文

$N$ 頂点 $M$ 辺の有向グラフが与えられます。頂点には $1$ から $N$ まで、辺には $1$ から $M$ までの番号が付けられています。このグラフには多重辺が存在することがありますが、自己辺は存在しません。

辺 $i$ は頂点 $u_i$ から頂点 $v_i$ へ向かう辺であり、この辺を削除するには $c_i$ のコストがかかります。

$0$ 本以上の辺を削除して、頂点 $S$ から頂点 $T$ へ到達できないようにします。このとき、削除する辺のコストの合計の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられます。

$N\ M\ S\ T$
$u_1\ v_1\ c_1$
$u_2\ v_2\ c_2$
$\vdots$
$u_M\ v_M\ c_M$

制約

• $2 \leq N \leq 2000$
• $1 \leq M \leq 10000$
• $1 \leq S,T \leq N$
• $S \neq T$
• $1 \leq u_i,v_i \leq N$
• $u_i \neq v_i$
• $1 \leq c_i \leq 10^9$
• 入力される値はすべて整数

出力

頂点 $S$ から頂点 $T$ へ到達できないようにするために必要なコストの合計の最小値を出力してください。

出力の末尾に改行してください。

サンプル

4 5 1 4
1 2 3
1 3 2
2 3 1
2 4 2
3 4 4

5

3 5 1 3
1 2 4
1 2 7
2 3 20
1 3 3
3 1 100

14

5 4 2 5
2 1 8
1 3 4
4 5 9
5 4 2

0