問題文

MojaCoder国は $1$ から $N$ までの番号のついた $N$ 個の都市と $M$ 本の道路からなり、道路 $i$ $(1\leq i\leq M)$ は都市 $A_i$ と $B_i$ を双方向に結んでおり、通行には $C_i$ 日かかります。 また、都市 $1$ はriano王国との国境に位置する都市であり、都市 $N$ は首都です。

ある日、riano王国の軍が攻めてきました。あなたは、この軍が首都に到達するまでの時間をできるだけ長く稼ぐために、国内の道をあらかじめいくつか（ $0$ 本以上）破壊することにしました。 その際、破壊後において

• MojaCoder国の任意の $2$ 都市間を、いくつかの破壊されていない道路を通って相互に行き来できる

という状態にしておく必要があります。なお、道路を破壊する前の状態でこの条件が成り立つことは保証されています。

都市 $1$ から都市 $N$ までの侵攻にかかる日数は最大何日まで引き延ばせるでしょうか。 ただし、riano王国軍は道路以外を通行せず、破壊されていない道路のみを使ったときの最短経路で侵攻するものとし、また道路を通過する以外の一切の行為にかかる時間は無視します。

制約

• $2 \leq N \leq 16$
• $N-1\leq M \leq N(N-1)/2$
• $1\leq A_i,B_i\leq N$ かつ $A_i\neq B_i$ $(1\leq i\leq M)$
• $i\neq j$ のとき $(A_i,B_i)\neq(A_j,B_j)$ かつ $(A_i,B_i)\neq(B_j,A_j)$
• $1\leq C_i\leq 10^8$ $(1\leq i\leq M)$
• 入力は全て整数である
• 入力において任意の $2$ 都市間はいくつかの道路をつかって結ばれている

入力

$N$ $M$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

...

$A_M$ $B_M$ $C_M$

出力

答えを出力してください。

サンプル

3 3
1 2 5
1 3 12
2 3 4

12

道路 $3$ を破壊すると、図のような道路状況になり、都市 $1$ から $3$ $(=N)$ までの通行所要時間は $12$ 日になります。 ここで、都市 $2$ は孤立してはいけませんが、都市 $1$ と都市 $3$ を結ぶ途上にある必要はありません。（図のようになってもよいです。）

8 8
5 1 43466
2 8 181586
3 4 183906
3 5 150499
4 5 67463
4 8 65445
6 5 8409
5 7 30014

443316

都市 $4,5$ 間の道路を破壊するのが最適です。