問題文

頂点に $1$ から $N$ までの、辺に $1$ から $M$ までの番号のついた、$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。 辺 $i$ は頂点 $u_i$ と $v_i$ を重み $w_i$ で双方向に結んでいます。

ある頂点から出発して、すべての頂点をちょうど $1$ 度ずつ通り、出発点に戻るような巡回路であって、その重みが最小であるようなものの重みを求めてください。

この問題の制約下で、そのような巡回路が少なくとも $1$ つ存在することが示せます。

入力

$N\ M$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_M\ v_M\ w_M$

• 入力はすべて整数
• 与えられるグラフは単純かつ連結
• $2 \leq N \leq 500$
• $M=\displaystyle \frac{N(N-1)}{2}$
• $1 \leq u_i,v_i \leq N$
• $w_i=1$

出力

問題文の条件を満たす巡回路の重みの最小値を $1$ 行に出力してください。

最後に改行してください。

サンプル

2 1
1 2 1

2