問題文

幼少のパンチくんは、全部で $N$ 店あるお菓子やさんを巡ろうとしています。

このうちのいくつかの店では、スタンプをカードに押してもらえます。その店のスタンプがあると、さらに別のいくつかの店で、ボーナスのお菓子がもらえるというシステムです。

ただし、パンチくんは一度行った店には $2$ 回行きたくありません。そのため、例えば

• 店 $A$ のスタンプがあると、店 $B$ でお菓子が $3$ 個もらえる
• 店 $B$ のスタンプがあると、店 $A$ でお菓子が $2$ 個もらえる

という $2$ つの条件が重なっている場合 、どちらかのお菓子を諦めなければいけません。この場合、後者を諦めて、前者の $3$ 個のお菓子をもらうのが得です。

パンチくんがもらえるお菓子の最大値はいくらでしょうか。

---

入力

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

$N$ $E$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ : $a_E$ $b_E$ $c_E$

• $1$ 行目には、お菓子屋さんの数を表す整数 $N (1 ≦ N ≦ 16)$ と、お菓子をもらえる店舗関係の数を表す整数 $E (0 ≦ E ≦ N×N)$がスペース区切りで与えられる。
• $2$ 行目から $E$ 行では、お菓子をもらえる店舗関係の情報が与えられる。
  このうち $i$ 行目では、 $3$ つの整数 $a_i (1 ≦ a_i ≦ N)$, $b_i (1 ≦ b_i ≦ N)$, $c_i (1 ≦ c_i ≦ 1000)$ が与えられる。
  これらは、「店 $a_i$ のスタンプがあると、店 $b_i$ にて、お菓子が $c_i$ 個もらえる」ということを表している。
• $i≠j$ のとき、 $a_i≠a_j$ または $b_i≠b_j$ であることが保障されている。

部分点

$1 ≦ N ≦ 8$ を満たすテストケースに正解した場合、部分点として $130$ 点が与えられる。

出力

パンチくんがもらえるお菓子の最大値を、 $1$ 行で出力せよ。出力の末尾には改行をいれること。

---

入力例1

2 2
1 2 3
2 1 2

出力例1

3

問題文に記載されている例です。

---

入力例2

4 3
1 2 10
1 3 20
1 4 30

出力例2

60

全てのお菓子をもらうことが出来ます。

---

入力例3

3 3
1 2 20
2 3 30
3 1 10

出力例3

50

$10$ 個のお菓子を諦めることで、最大値を得ます。

---

入力例4

16 1
4 4 1000

出力例4

0

同じ店に $2$ 回行くことはできないので、お菓子はもらえません。また、このスタンプサービスと関係ない店がいくつかあることもあります。

---

入力例5

4 6
4 1 3
1 3 3
4 2 3
3 4 2
2 3 3
2 2 10

出力例5

12

---