AT_donuts_live2014_5 お菓子やさん

幼年的パンチくん打算去巡游总共 $N$ 家糖果店。 其中有几家店可以在卡片上盖章。如果拥有某家店的印章，在另外一些店里可以获得额外的糖果。 但是，パンチくん不想去同一家店两次。因此，例如： - 如果有店 $A$ 的印章，在店 $B$ 可以获得 $3$ 个糖果； - 如果有店 $B$ 的印章，在店 $A$ 可以获得 $2$ 个糖果； 这两种条件同时存在时，必须放弃其中一项糖果。在这种情况下，放弃后者，获得前者的 $3$ 个糖果是最划算的。 请问パンチくん最多能获得多少个糖果？

输入通过标准输入按以下格式给出。 > $N$ $E$ > $a_1$ $b_1$ $c_1$ > $a_2$ $b_2$ $c_2$ > $\vdots$ > $a_E$ $b_E$ $c_E$ - 第 $1$ 行包含两个用空格分隔的整数 $N\ (1\leq N\leq 16)$，表示糖果店的数量，以及 $E\ (0\leq E\leq N\times N)$，表示可以获得糖果的店铺关系数。 - 接下来的 $E$ 行，每行包含三个整数 $a_i\ (1\leq a_i\leq N)$，$b_i\ (1\leq b_i\leq N)$，$c_i\ (1\leq c_i\leq 1000)$，表示“如果有店 $a_i$ 的印章，在店 $b_i$ 可以获得 $c_i$ 个糖果”。 - 保证当 $i\neq j$ 时，$a_i\neq a_j$ 或 $b_i\neq b_j$。

输出パンチくん最多能获得的糖果数量，输出一行，末尾需换行。

## 部分分 如果能正确解决 $1\leq N\leq 8$ 的测试用例，将获得 $130$ 分的部分分数。 ## 样例解释 1 这是题目描述中给出的例子。 ## 样例解释 2 可以获得所有的糖果。 ## 样例解释 3 通过放弃 $10$ 个糖果，可以获得最大值。 ## 样例解释 4 由于不能去同一家店两次，无法获得糖果。另外，也可能存在与这个印章服务无关的店铺。 由 ChatGPT 4.1 翻译