U644153 图的染色

给定一个包含 $n$ 个点 $m$ 条边的简单无向图（$2 \le n \le 30, 1 \le m \le \frac{n \cdot (n-1)}{2}$）。 第 $i$ 条边连接两个节点 $u_i$ 和 $v_i$，边权为 $w_i$（$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^7$）。 你需要使用黑色和白色两种颜色给图中所有的点染色（每个点必须染成黑色或者白色中的一种颜色），你希望使图中所有连接两个不同颜色点的边的权值之和最大。 求：所有染色方案中，连接两个不同颜色节点的边的边权和的最大值。

第一行，两个整数 $n$ 和 $m$（$2 \le n \le 30, 1 \le m \le \frac{n \cdot (n-1)}{2}$）。 接下来 $m$ 行，每行包含三个整数 $u_i, v_i, w_i(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^7)$，表示有一条连接节点 $u_i$ 和 $v_i$ 的长度为 $w_i$ 的边。

输出一个整数，表示所有染色方案中，连接两个不同颜色节点的边的边权和的最大值。

#### 样例解释 一种最优解是将节点 $1$ 和 $3$ 染成黑色，将节点 $2$ 染成白色，则所有满足条件的边对应的边权和为 $2 + 3 = 5$。 #### 数据规模与约定 - 对于 $30\%$ 的数据，$n \le 10$ - 对于 $60\%$ 的数据，$n \le 20$ - 对于 $100\%$ 的数据，$2 \le n \le 30, 1 \le m \le \frac{n \cdot (n-1)}{2}$