问题描述

幼小的小朋友Panji先生计划要游览一共N个糖果店。

其中有一些店可以在卡上盖章。拥有该店的章时，在其他一些店可以获得额外的糖果奖励。

然而，Panji先生不想再去一次同一家店。所以，例如：

• 如果店A有章，那么他可以在店B获得3个糖果。
• 如果店B有章，那么他可以在店A获得2个糖果。

在这种情况下，他必须放弃后者，选择前者的3个糖果。

Panji先生能够获得的最大糖果数量是多少呢？

---

输入

输入将从标准输入读取，并具有以下格式。

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

• 第一行包含两个整数，分别表示糖果店的数量$N(1 ≤ N ≤ 16)$和可以获得糖果奖励的店铺关系数量$E(0 ≤ E ≤ N×N)$。
• 接下来的$E$行中，给出了可获得糖果奖励的店铺关系的信息。
  • 每行包含三个整数$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分。

输出

请以一行输出Panji先生能够获得的最大糖果数量。在输出末尾加上换行符。

---

示例输入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

由于不可重复访问同一家店，因此无法获得糖果。此外，存在一些与该章鼓励活动无关的店铺。

---

示例输入5

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

示例输出5

12