你正在计划一次穿越一些有趣但众所周知的地形的长途徒步旅行。你有 $N$ 个想要参观的有趣地点，以及 $M$ 条连接这些地点的路径。每条路径都有一个正整数表示的难度等级。

然而，这个路径系统有些特殊。恰好有 $N-1$ 条难度等级为 1 的路径（这些是完全平坦的路径），其余路径的难度等级至少为 $\lceil \frac{N}{3} \rceil$（这些是非常崎岖的山路）。（$x$ 的向上取整，记作 $\lceil x \rceil$，是大于或等于 $x$ 的最小整数。）

此外，仅使用难度等级为 1 的路径，可以在任意两个地点之间通行。

你希望参观每一个地点，从你选择的任意地点出发，并在某个其他地点结束，使得你至少访问每个地点一次，且所有路径的难度等级总和在所有可能的行走路线中最小。注意，将一条难度等级为 $d$ 的路径走 $k$ 次，对难度等级总和的贡献为 $k \cdot d$。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ ($4 \le N \le 500\,000$) 和 $M$ ($N-1 \le M \le 2\,000\,000$)。

接下来的 $M$ 行，每行包含三个空格分隔的整数 $x_i, y_i$ 和 $w_i$，描述连接地点 $x_i$ 和 $y_i$ 的难度等级为 $w_i$ 的路径 ($1 \le i \le M; 0 \le x_i, y_i \le N-1; x_i \neq y_i$)。注意，每对地点之间最多只有一条路径，且 $w_i = 1$ 或 $\lceil \frac{N}{3} \rceil \le w_i \le N$。

子任务

• 对于 25 分中的 1 分，满足 $N \le 6$ 且 $M \le 10$。
• 对于 25 分中的额外 2 分，满足 $N \le 20$ 且 $M \le 40$。
• 对于 25 分中的额外 2 分，满足 $N \le 5\,000, M \le 10\,000$，且 $w_i = 1$ 或 $\lceil \frac{N}{2} \rceil \le w_i \le N$。
• 对于 25 分中的额外 6 分，满足 $N \le 100$ 且 $M \le 200$。
• 对于 25 分中的额外 2 分，满足 $N \le 500$ 且 $M \le 1\,000$。
• 对于 25 分中的额外 3 分，满足 $N \le 5\,000$ 且 $M \le 10\,000$。
• 对于 25 分中的额外 5 分，满足 $N \le 80\,000$ 且 $M \le 160\,000$。

输出格式

输出一个整数，表示为了至少访问每个地点一次所走过的所有路径的最小难度等级总和。

样例

输入 1

9 10
0 1 1
0 2 1
0 3 1
1 4 1
2 5 1
2 6 1
3 7 1
3 8 1
2 4 5
6 7 3

输出 1

11

说明 1

这是平坦路径的集合：

这是所有难度等级路径的完整集合：

这是省略了难度等级为 1 的路径后的完整路径集合：

对于这组路径，一条最优的行走路线是 $4 \to 1 \to 0 \to 2 \to 5 \to 2 \to 6 \to 7 \to 3 \to 8$，总代价为 $1 + 1 + 1 + 1 + 1 + 1 + 3 + 1 + 1 = 11$。没有其他方式可以在至少访问每个地点一次的情况下，获得更低的难度等级总代价。