E - お菓子やさん Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

幼少のパンチくんは、全部で 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