P12593 沉石鱼惊旋

> 绝代有佳人，幽居在空谷。

小 C 有一张 $n$ 个点 $m$ 条边的简单无向带权连通图 $G$。 现在你可以进行 $n$ 次操作，每次操作如下： 选择一个仍未被删除的点 $u$，然后删除点 $u$ 和当前与 $u$ 相连的所有边（即其中一个端点是 $u$ 的边）。假设本次删除的边的边权分别是 $w_1, w_2,\dots w_k$，则本次操作的代价是 $k\times (w_1+w_2+\dots+w_k)$。 你的总代价是这 $n$ 次操作的代价和。 显然 $n$ 次操作后，所有的边和点都将被删除。现在小 C 想知道，将图中所有点和边都删除（即把图删空）的最小总代价是多少。当然，在过程中你不需要保证图每次操作后仍然连通。 > 天寒翠袖薄，日暮倚修竹。

第一行，两个整数 $n,m$。 接下来的 $m$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的边。

一行，一个整数，表示删空图 $G$ 的最小代价。

在样例 1 中，这张图有 $8$ 条边：$(1,3,10),(1,5,20),(1,6,30),(2,5,10),(2,6,20),(3,4,30),(3,5,10),(5,6,20)$。一个可行的最优策略如下： - 选择 $u=4$ 删除，花费 $1\times (30)=30$ 的代价。 - 选择 $u=3$ 删除，花费 $2\times (10+10)=40$ 的代价。 - 选择 $u=2$ 删除，花费 $2\times (10+20)=60$ 的代价。 - 选择 $u=5$ 删除，花费 $2\times (20+20)=80$ 的代价。 - 选择 $u=6$ 删除，花费 $1\times (30)=30$ 的代价。 - 选择 $u=1$ 删除，没有边，花费 $0$ 的代价。 故总代价为 $30+40+60+80+30+0=240$。 --- - 对于 $10\%$ 的数据，边权 $w=1$。 - 对于另外 $20\%$ 的数据，$m=n-1$。 - 对于 $100\%$ 的数据，$1\leq n\leq 8$，$n-1\leq m\leq \frac{n(n-1)}{2}$，$1\leq u,v\leq n$，$1\leq w\leq 10^9$。保证图中没有重边和自环。