P1029沧溟探秘藏（treasure）

【题目背景】

灵舵载着 Gioush 大队穿过特西荼亚海的千重岛影，金白色鱼群最终停在一片沉没遗迹上方。为了查明落日异象与鱼群迁徙共同指向这里的原因，Ehundategh 决定带领众人进入遗迹深处。

【题目描述】

沉没遗迹中共有 $n$ 间遗室，编号为 $1$ 至 $n$。遗室之间残留着 $m$ 条双向通道，第 $i$ 条通道连接遗室 $u_i$ 与 $v_i$，其长度为 $w_i$。这些通道保证任意两间遗室都能相互抵达。

由于每条新通道都只能从已经清理完成的遗室向外开辟，越向遗迹深处推进，运输器材需要经过的已探索区域就越多，所以 Gioush 大队需要在选择通道的同时，考虑每间遗室距离入口的层数。

探索开始前，Ehundategh 可以选择任意一间遗室作为遗迹入口。遗迹入口最先完成清理，其探索层数为 $0$。

此后，每次探索都需要选择一间已经完成清理的遗室 $u$、一间尚未清理的遗室 $v$，以及一条直接连接 $u,v$ 的通道。若 $u$ 的探索层数为 $k$，那么沿这条通道完成对 $v$ 的清理后，$v$ 的探索层数为 $k+1$；若该通道的长度为 $w$，本次探索产生的开辟代价为 $w\times(k+1)$。

当所有遗室都完成清理时，本次探索过程称为一个探索方案。一个探索方案的总代价，等于其中每次探索产生的开辟代价之和。

Ehundategh 想知道，在所有可能的遗迹入口与探索方案中，总代价最小是多少。

【输入格式】

从文件 $\textbf{\textit{treasure.in}}$ 中读入数据。

第一行两个整数 $n,m$，分别表示遗室的数量和双向通道的数量。

接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接遗室 $u,v$ 的双向通道，其长度为 $w$。

同一对遗室之间可能存在多条通道。

【输出格式】

输出到文件 $\textbf{\textit{treasure.out}}$ 中。

输出一行一个整数，表示所有探索方案中最小可能的总代价。

【样例 1 输入】

14 521 2 131 3 341 4 152 3 463 4 1

【样例 1 输出】

14

【说明/提示】

【样例 1 解释】

选择 $4$ 号遗室作为遗迹入口，先通过长度为 $1$ 的通道清理 $1$ 号和 $3$ 号遗室，再从 $1$ 号遗室通过长度为 $1$ 的通道清理 $2$ 号遗室。三次探索产生的开辟代价依次为 $1,1,2$，总代价为 $4$。

可以证明，不存在总代价更小的探索方案。

【样例 2】

见选手目录下的 $\textbf{\textit{treasure/treasure2.in}}$ 和 $\textbf{\textit{treasure/treasure2.ans}}$。

该组样例符合测试点 $4\sim 6$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{treasure/treasure3.in}}$ 和 $\textbf{\textit{treasure/treasure3.ans}}$。

该组样例符合测试点 $7\sim 10$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{treasure/treasure4.in}}$ 和 $\textbf{\textit{treasure/treasure4.ans}}$。

该组样例符合测试点 $11\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{treasure/treasure5.in}}$ 和 $\textbf{\textit{treasure/treasure5.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证：$1\leq n\leq 12$，$0\leq m\leq 10^3$，$1\leq u_i,v_i\leq n$，$u_i\neq v_i$，$1\leq w_i\leq 5\times 10^5$，任意两间遗室均能通过给出的通道相互抵达。

特殊性质：对于连接同一对遗室的通道，只保留其中代价最小的一条后，剩余通道恰好构成一棵树。