E: いたずらされたグラフ

問題

あなたはグラフのアルゴリズムとして典型であるフローの問題を解いていた。
その問題で与えられるグラフは、頂点 $N$ 個、辺 $M$ 本であり、頂点 $x_i$ から 頂点 $y_i$ に容量 $z_i$ 、コスト $d_i$ の辺が張られている。 ところが、AORイカちゃんが入力ケースにいたずらした。 その結果、 $x_i, y_i, z_i$ の順序がシャッフルされ、頂点の情報と容量の情報が区別できなくなってしまった。

そこで、あなたは $s-t$ 間のフローを求めることを諦め、 $s-t$ 間の最短距離を求めることにした。 あなたは、 $x_i, y_i, z_i$ の順序がシャッフルされた入力ケース $a_i, b_i, c_i$ のうちから二つを頂点情報にし、コスト $d_i$ の辺を張ることにした。つまり、$a_i$ から $b_i$, $a_i$ から $c_i$, $b_i$ から $c_i$ の三つの候補のうち一つにコスト $d_i$ の辺を張る。

考えられるグラフのうち、 「s から t への最短距離」の最小値を求めよ。

制約

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le s,t \le N$
• $1 \le a_i,b_i,c_i \le N$
• $1 \le d_i \le 10^9$
• $s \neq t$
• 元のグラフにおいて $s$ から $t$ への経路が存在する
• 入力は全て整数

入力

$N \ M \ s \ t$
$a_1 \ b_1 \ c_1 \ d_1$
$\vdots$
$a_M \ b_M \ c_M \ d_M$

出力

考えられるグラフのうち、 「$s$ から $t$ への最短距離」の最小値を一行で出力せよ。また末尾に改行を出力せよ。

サンプル

サンプル入力 1

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

サンプル出力 1

7

サンプル入力 2

8 5 8 3
4 5 1 2
5 6 2 3
7 8 5 12
3 1 2 11
1 2 3 10

サンプル出力 2

24