体力作りで $N$ 頭（$(2 \le N \le 1,000,000)$）が牧場の $T$ 道（$(2 \le T \le 100)$）を使うリレーをします。

道は異なる二交差点（$(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$）を結び、各交差点に最低二道あります。長さ $length_i$（$(1 \le length_{i} \le 1,000)$）と両端が既知で、同じ二点を直接結ぶ二道はありません。数学的なグラフです。

$N$ 頭を交差点に配置し、同じ点に複数頭も可能です。順にバトンを渡して正しいゴールに届く配置が必要です。

配置を助け、開始 $S$ と終了 $E$ を結び、正確に $N$ 道を通る最短経路を求めてください。

入力

• 第 $1$ 行：空白区切り整数 $N$、$T$、$S$、$E$。

• 第 $2..T+1$ 行：第 $i+1$ 行は道 $i$ を三整数 $length_i$、$I1_i$、$I2_i$ で記述。

出力

• 第 $1$ 行：$S$ から $E$ へ正確に $N$ 道を通る最短距離を整数一つ。

入出力例

入力 1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

出力 1

10

問題作成者：Erik Bernhardsson、2003