Problem Statement

高橋君の住む街には $N$ 個の家と $M$ 個の道があります。 家は $1$ ～ $N$ の整数によって番号付けされています。 高橋君は家 $1$ に住んでいます。 道も $1$ ～ $M$ の整数によって番号付けされています。 $i$ 番目の道は家 $u_i$ と 家 $v_i$ を双方向につなぐ長さ $l_i$ メートルの道です。

高橋君は街のどこかの家に居るという「幸せの青い鳥」を探しています。 実は、「幸せの青い鳥」は高橋くんの家にいて、高橋君もそのことを知っています。 しかし、形だけでも探す旅に出ないと盛り上がりに欠けて面白くないので、仕方なく旅の計画をたてることにしました。

高橋君は自分の家から開始して、同じ道を二度以上通らないようにいくつかの家に訪れ、最後に自分の家に戻ってくる、という旅の計画をたてる予定です。 このとき盛り上がりを作るために、旅の途中で自分の家以外の家を少なくとも $1$ 軒訪れる予定です。 高橋君はこの茶番をできるだけ早く終わらせたいので、通る道の長さの総和が最も小さくなるような計画が最適だと考えています。

高橋君の住む街の家と道の情報が与えられるので、高橋君が上の条件のもとで最適な計画をたてることができるかどうかを求めてください。 もし最適な計画をたてることができるならば、そのとき通る道の長さの総和を求めてください。

Input

入力は以下の形式で標準入力から与えられる

N M
u_1 v_1 l_1
u_2 v_2 l_2
:
u_M v_M l_M

• $1$ 行目には高橋君の住む街にある家の個数 $N(3 ≦ N ≦ 300)$ と 道の本数 $M(3 ≦ M ≦ N(N-1)/2)$ が空白区切りで与えられる。
• $2$ 行目からの $M$ 行のうち $i$ 行目には $i$ 番目の道路が結ぶ家の番号 $u_i, v_i(1 ≦ u_i ＜ v_i ≦ N)$ とその長さを表す整数 $l_i(1 ≦ l_i ≦ 10^5)$ が空白区切りで与えられる。
• $i ≠ j$ ならば $u_i ≠ u_j$ または $v_i ≠ v_j$ の少なくとも一方が成り立つ。

Output

最適な計画をたてることができないならば $-1$ を、できるならばそのとき通る道の長さの総和を $1$ 行に出力せよ。出力の末尾にも改行を入れること。