有向图 $G=(V,E)$ 强连通当且仅当可以通过以下方法构造：

1. 任选一个点 $s$，令 $S=\{s\}$。
2. 重复以下过程直到 $S=V$。
   1. 任选两个点 $u,v\in S$。$u$ 和 $v$ 可以相同。
   2. 选择 $k\pod{k\ge 0}$ 个不同的点 $w_1,w_2,\ldots,w_k\not\in S$。
   3. 连接 $u\to w_1\to w_2\to\cdots\to w_k\to v$，并将 $w_1,w_2,\ldots ,w_k$ 加入 $S$。

这个方法被称作耳分解，路径 $u\to w_1\to w_2\to \cdots \to w_k\to v$ 被称作耳。

由于本题只要求权值和最小，我们可以要求每次至少加入一个点 (即 $k\ge 1$)，加入点时考虑它和已加入点之间的所有边，不在路径上的边取两个方向的较小值即可。

设 $f[S]$ 表示已经加入点集 $S$ 的最小代价；$g[S][u][v]$ 表示当前加入了点集 $S$，还需加入 $u$ 到 $v$ 的一条路径，最小的代价。枚举下一个点是哪个即可转移。

时间复杂度 $O(N^32^N)$。