AT_donuts_live2014_5 お菓子やさん

[problemUrl]: https://atcoder.jp/contests/donuts-live2014/tasks/donuts_live2014_5 幼少のパンチくんは、全部で $ 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 $ 行で出力せよ。出力の末尾には改行をいれること。

### 部分点 $ 1\ ≦\ N\ ≦\ 8 $ を満たすテストケースに正解した場合、部分点として $ 130 $ 点が与えられる。 ### Sample Explanation 1 問題文に記載されている例です。 ### Sample Explanation 2 全てのお菓子をもらうことが出来ます。 ### Sample Explanation 3 $ 10 $ 個のお菓子を諦めることで、最大値を得ます。 ### Sample Explanation 4 同じ店に $ 2 $ 回行くことはできないので、お菓子はもらえません。また、このスタンプサービスと関係ない店がいくつかあることもあります。