题目描述

小可管理着一个由 $n$ 个节点和 $m$ 条通信线路组成的网络。每个通信线路连接两个不同的节点，并有一个维护成本 $w$。网络初始时是连通的。

现在小可需要逐步关闭所有节点。每次操作，他可以选择一个尚未关闭的节点 $u$，然后关闭该节点以及所有与 $u$ 相连的通信线路。假设本次关闭的线路的维护成本分别为 $w_1, w_2, \dots, w_k$，那么本次操作的消耗为 $k \times (w_1 + w_2 + \dots + w_k)$。

总消耗是所有操作的消耗之和。

显然，经过 $n$ 次操作后，所有节点和线路都将被关闭。小可想知道，关闭整个网络的最小总消耗是多少？注意，在操作过程中，网络不需要保持连通。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示节点 $u$ 和节点 $v$ 之间有一条维护成本为 $w$ 的通信线路。

输出格式

一行一个整数，表示关闭整个网络的最小总消耗。

样例

6 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

240

样例解释

样例解释 1

在样例中，网络有 $8$ 条线路，具体见输入。一种最优策略如下：

• 关闭节点 $4$，消耗 $1 \times (30) = 30$。
• 关闭节点 $3$，消耗 $2 \times (10 + 10) = 40$。
• 关闭节点 $2$，消耗 $2 \times (10 + 20) = 60$。
• 关闭节点 $5$，消耗 $2 \times (20 + 20) = 80$。
• 关闭节点 $6$，消耗 $1 \times (30) = 30$。
• 关闭节点 $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$。保证没有重边和自环。