题目描述

Laura 和 Kruskal 被任命为某个国家交通网络的共同管理者。这个国家的名字是保密的。该交通网络由 N 个城市组成，编号为 1..N，并由 M 条双向道路连接。

这些道路目前全都是二级公路，而人们希望它们能变成一级公路。于是管理者们打算选择一些道路进行升级。为此，他们手上有一份很长的卷轴，上面按顺序列出了该国所有道路；对于每条道路，都给出了它连接的两个城市，以及将其升级为一级公路所需的施工时间（以月为单位）。

交通部非常有钱，所以所有施工都可以同时开始。现在他们要决定选择哪些道路进行升级。

• Kruskal 希望被升级的道路能够使得任意两个城市之间都能仅通过一级公路互相到达；
• Laura 则担心这样会让施工时间拖得太久。

他们讨论了很久，最后决定采用一种折中评价方式：

• Laura 对一个道路集合的评价是：其中施工时间最长的那条道路的施工时间；
• Kruskal 对同一个道路集合的评价是：由 N 个城市和所选道路组成的图中的连通块个数。

两个人都希望最小化自己的评价，于是他们将这两个评价相乘，并把这个乘积作为最终需要最小化的“折中评价”。

但他们已经没有时间去精挑细选某一组道路了。现在他们唯一来得及做的事情，就是从卷轴中截取一个非空的连续子段，并把这段子段中的道路送给施工公司。

请你编写程序 compromise，读入整张卷轴上的道路列表，并求出：在所有可能的非空连续子段中，折中评价的最小值是多少。

输入格式

第一行两个整数 N 和 M，表示城市数和道路数。
接下来 M 行，每行三个整数 ui, vi, ti，表示列表中的第 i 条道路连接城市 ui 和 vi，其施工时间为 ti。

输出格式

输出一行一个整数，表示最小可能的折中评价。

数据范围

• 1 ≤ N, M ≤ 500000
• 1 ≤ ui, vi ≤ N
• 1 ≤ ti ≤ 10^12
• 当 i ≠ j 时，ti ≠ tj
• 注意：给出的图不一定连通，并且可能含有自环和重边。

子任务与评分

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。

• 子任务 1（11 分）：N, M ≤ 6500
• 子任务 2（23 分）：N, M ≤ 20000；t 的大小规律是随机生成的。更形式化地说：当 pi > pj 时有 ti > tj，其中 p 是 1..M 的一个随机排列。
• 子任务 3（25 分）：N, M ≤ 100000
• 子任务 4（41 分）：无额外限制

样例输入

6 9
3 3 4
1 2 11
4 5 6
2 4 7
3 6 9
5 2 10
2 1 5
3 1 21
1 4 8

样例输出

20

样例解释

最优的连续子段由以下道路组成：4-5、2-4、3-6、5-2、2-1。

其中，5-2 的施工时间最长，为 10 个月。

此时图中有两个连通块：第一个为 {1, 2, 4, 5}，第二个为 {3, 6}。

因此这段子段的折中评价为：

10 × 2 = 20