瘟疫公司 - 問題

世界是一个由 $n$ 个城市，$m$ 条交通路线组成的联通图。每条交通路线有一个权值。定义一个联通子图的权值 $w(s)$ 是子图的最小生成树权值和与最大生成树权值和的异或和。

注意：

$w(s)$ 仅对图 $G$ 的联通子图 $(s,E_s)$ 才有定义；
联通子图 $(s,E_s)$，其中点集为 $s$，边集 $E_s = \{(u,v)\in s\}$ 为所有两端点都属于 $s$ 的边的集合，联通即满足 $s$ 中的任意两点可以被若干 $E_s$ 中的边所联通

你最初可以任选一个城市开始发展。假设你目前感染的城市点集是 $S$，下一步扩张的点集是 $T$（只需保证 $S \subset T$，且 $T$ 联通），那么称这一步的 DNA 点数消耗是 $(|T| − |S |)\times w(T)$。

请找到一条感染计划，即一个点集序列 $S_1 \subset S_2 \subset... \subset S_k$，其中 $S_1$ 只包含一个城市，$S_k$ 包含所有城市，每一步都要保证集合是联通的，最小化扩张的总 DNA 点数消耗。

第一行两个正整数 $n, m$，表示城市数量和道路数量。

接下来 $m$ 行，每行 3 个正整数 $u,v,w$，表示一条交通路线。

输出一行一个正整数，为最小 DNA 代价。

见下发文件

见下发文件

对于 100% 的数据，$1\le n \le 20, 1\le m \le 100,1\le w \le 10000$，保证图连通

子任务1（20pts）：$n\le 3, m\le 10$

子任务2（10pts）：$n\le 4, m\le 10$

子任务3（10pts）：$n\le 5, m\le 10$

子任务4（20pts）：$n\le 10, m\le 100$

子任务5（20pts）：$n\le 16, m\le 100$

子任务6（20pts）：$n\le 20, m\le 100$

QOJ.ac