問題文

映像制作班のメンバーは、吊り橋巡りの動画を撮影しようと山奥へ赴いています。

この場所には $N$ 個の地点と、それらを結ぶ $M$ 本の吊り橋があります。
各地点は地点 $1$ 、地点 $2$ 、$\cdots$、地点 $N$ 、各吊り橋は橋 $1$ 、橋 $2$ 、$\cdots$、橋 $M$ と名付けられており、橋 $i(1 \leq i \leq M)$ は地点 $A_i$ と地点 $B_i$ を双方向に結んでいます。
ここで、橋の両端が同じ地点であることも、ある $2$ つの地点の間が $2$ 本以上の橋で直接結ばれていることもありません。

また、 $M$ 本の吊り橋の中には $N$ 本の「有名な吊り橋」が含まれており、それらはそれぞれ地点 $1$ と地点 $2$ 、地点 $2$ と地点 $3$ 、$\cdots$、地点 $N$ と地点 $1$ を結んでいます。

映像制作班のメンバーは、好きな地点から撮影を開始し、撮影を続けたまま吊り橋を通って他の地点に進むことを繰り返し、最後に撮影を開始した地点に戻ってきて撮影を終了します。
映像制作班の目的は、その間の撮影での「映え度」という値の総和を最大化することです。

「映え度」とは、各吊り橋を撮影したときに動画が映える度合いを表す値であり、
各 $i(1 \leq i \leq M)$ に対し、橋 $i$ を撮影したときに得る「映え度」は $C_i$ です。

撮影の過程で、 $N$ 本の「有名な吊り橋」は絶対に撮影しなくてはいけません。
また、同じ景色を撮っても面白くないので、同じ吊り橋を二度撮影してはいけません。
ただし、同じ地点を複数回通ることはしても構いません。

この条件の下、適切に撮影ルートを決めることで、「映え度」の総和を最大化してください。

制約

• $3 \leq N \leq 16$
• $N \leq M \leq N(N-1)/2$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^6$
• 各 $i(1 \leq i \leq M)$ に対し、$A_i \neq B_i$
• $i \neq j$ ならば $\lbrace A_i , B_i \rbrace \neq \lbrace A_j , B_j \rbrace$
• 各 $i(1 \leq i \leq N)$ に対し、 $j(1 \leq j \leq M)$ が存在して、 $A_j = i$ かつ $B_j=i+1$
  (ただし、$i = N$ のときは $A_j = N , B_j = 1$ とする)
• 入力は全て整数

入力

出力

得ることのできる「映え度」の総和の最大値を出力してください。

サンプル

6 14
2 4 10
2 6 6
1 3 1
2 3 5
1 5 6
5 6 7
1 4 2
6 4 1
3 4 7
6 1 6
3 5 4
1 2 5
4 5 5
2 5 1

63

たとえば、地点$1$から始めて
橋$5$→橋$13$→橋$1$→橋$12$→橋$3$→橋$11$→橋$6$→橋$8$→橋$9$→橋$4$→橋$2$→橋$10$
というルートで撮影を行うことで、「映え度」の総和を63にすることができます。
同じ吊り橋を二度通ることはできないが、同じ地点は何度通ってもよいことに注意してください。

3 3
2 3 10
3 1 9
1 2 6

25

8 19
3 4 1
1 2 10
8 1 9
5 8 9
3 6 4
4 5 6
8 4 5
3 5 10
6 1 9
7 8 5
4 2 2
8 3 10
5 6 4
5 7 10
7 4 9
6 7 5
1 4 1
1 3 9
2 3 3

109