题目描述

探险家小铭得到一张古老地图，上面标着 $n$ 座深埋地下的宫殿，以及宫殿之间可供开凿的 $m$ 条通道和它们的长度。

小铭想把所有宫殿里的珍宝都挖出来。可是每座宫殿离地面都很远，从地面垂直打通一条竖井非常困难，而开凿宫殿之间的水平通道要容易得多。

装备商被他的计划打动，决定免费帮他打一口从地面直达某座宫殿的竖井，具体通到哪座宫殿由小铭自己决定。

在此之后，小铭要规划如何开凿宫殿之间的通道。已凿通的通道可以任意通行，不再产生代价；每凿通一条新通道，他就能挖到由这条通道新到达的宫殿里的珍宝。另外，他不想开凿无用的通道——两端宫殿都已被挖掘过的通道无需再开凿。

开凿一条新通道的代价为 $L\times K$：$L$ 是这条通道的长度，$K$ 是从装备商打通的那座宫殿出发、沿着已规划路线到达这条通道起点宫殿所经过的宫殿数量（起点宫殿与装备商打通的宫殿都计入）。

请编写程序，为小铭选定由装备商打通的宫殿以及之后开凿通道的方案，使工程总代价最小，并输出这个最小值。

输入格式

第一行两个用空格分开的正整数 $n,m$，表示宫殿的数量和通道的数量。

接下来 $m$ 行，每行三个用空格分开的正整数，依次为一条通道连接的两座宫殿的编号（编号为 $1\sim n$）以及这条通道的长度 $v$。

输出格式

一个正整数，表示最小的总代价。

样例

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

4

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

5

提示

【样例解释 $1$】

让装备商打通 $1$ 号宫殿。开凿通道 $1 \to 2$，挖到 $2$ 号宫殿；开凿 $1 \to 4$，挖到 $4$ 号宫殿；再开凿 $4 \to 3$，挖到 $3$ 号宫殿。

总代价为 $1 \times 1 + 1 \times 1 + 1 \times 2 = 4$。

【样例解释 $2$】

让装备商打通 $1$ 号宫殿。依次开凿 $1 \to 2$、$1 \to 3$、$1 \to 4$ 三条通道。

总代价为 $1 \times 1 + 3 \times 1 + 1 \times 1 = 5$。

【数据规模与约定】

对于 $20\%$ 的数据：保证输入是一棵树，$1 \le n \le 8$，$v \le 5\times 10^3$ 且所有的 $v$ 都相等。

对于 $40\%$ 的数据：$1 \le n \le 8$，$0 \le m \le 10^3$，$v \le 5\times 10^3$ 且所有的 $v$ 都相等。

对于 $70\%$ 的数据：$1 \le n \le 8$，$0 \le m \le 10^3$，$v \le 5\times 10^3$。

对于 $100\%$ 的数据：$1 \le n \le 12$，$0 \le m \le 10^3$，$v \le 5\times 10^5$。