Bessie は小さい農場に引っ越し、時々親友の一人を訪ねに戻ります。道の景色が好きで古い家に早く着きたくないので、最短でなく2番目に短い道を選びます。それは必ず存在すると知っています。

田舎には $R$ 本の双方向道路（$1 \le R \le 100,000$）があり、各々 $N$ 個の交差点（$1 \le N \le 5000$）中の2点を結びます。番号は $1..N$、出発点は1、友人の目的地は $N$ です。

2番目の道は最短のどれとも道路を共用でき、引き返して同じ道路や交差点を複数回通ってもよいです。最短より長い中で最短です。最短が複数あればそれらより長く、他のどの道よりも長くありません。

入力

1行目：空白区切りの2整数 $N$ と $R$。

$2..R+1$ 行目：各行は空白区切りの3整数 $A$、$B$、$D$。$A$ と $B$ を結ぶ長さ $D$（$1 \le D \le 5000$）の道です。

出力

1行目：1から $N$ への2番目に短い道の長さ。

入出力例

入力 1

4 4
1 2 100
2 4 200
2 3 250
3 4 100

出力 1

450

注記

ヒント

2経路：$1 \to 2 \to 4$（長さ $100+200=300$）と $1 \to 2 \to 3 \to 4$（長さ $100+250+100=450$）。