/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の住む街には N 個の家と M 個の道があります。 家は 1 ～ N の整数によって番号付けされています。 高橋君は家 1 に住んでいます。 道も 1 ～ M の整数によって番号付けされています。 i 番目の道は家 u_i と 家 v_i を双方向につなぐ長さ l_i メートルの道です。
高橋君は街のどこかの家に居るという「幸せの青い鳥」を探しています。 実は、「幸せの青い鳥」は高橋くんの家にいて、高橋君もそのことを知っています。 しかし、形だけでも探す旅に出ないと盛り上がりに欠けて面白くないので、仕方なく旅の計画をたてることにしました。
高橋君は自分の家から開始して、同じ道を二度以上通らないようにいくつかの家に訪れ、最後に自分の家に戻ってくる、という旅の計画をたてる予定です。 このとき盛り上がりを作るために、旅の途中で自分の家以外の家を少なくとも 1 軒訪れる予定です。 高橋君はこの茶番をできるだけ早く終わらせたいので、通る道の長さの総和が最も小さくなるような計画が最適だと考えています。
高橋君の住む街の家と道の情報が与えられるので、高橋君が上の条件のもとで最適な計画をたてることができるかどうかを求めてください。 もし最適な計画をたてることができるならば、そのとき通る道の長さの総和を求めてください。
入力
入力は以下の形式で標準入力から与えられる
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 の少なくとも一方が成り立つ。
出力
最適な計画をたてることができないならば -1 を、できるならばそのとき通る道の長さの総和を 1 行に出力せよ。出力の末尾にも改行を入れること。
入力例1
5 7 1 2 2 1 4 1 2 3 7 1 5 12 3 5 2 2 5 3 3 4 5
出力例1
13
家と道の様子は以下のようになります
1, 2, 5, 3, 4, 1 という順番に訪れる計画が最適です。 1, 2, 1 という順番に訪れる計画は 1 番目の道を 2 回通っているので条件を満たしていません。
入力例2
5 4 1 2 1 1 3 1 1 4 1 1 5 1
出力例2
-1
同じ道を 2 度以上通らない旅の計画をたてることはできません。よって -1 を出力します。
入力例3
10 12 1 4 3 1 9 1 2 5 4 2 6 1 3 7 5 3 10 9 4 7 2 5 6 6 5 8 5 6 8 3 7 9 5 8 10 8
出力例3
11