铺设暗网

Echo的代码留住了，但她的投影比以前更淡了——像一盏电压不足的灯，颜色从深蓝褪成了浅灰。CC几乎没离开过服务器旁边，有时说话，有时只是坐着，金属手指轻轻敲击着外壳。

"你在做啥子？"你问。

"陪她。"CC说，"她说过她能感知环境。我说话她应该能听见。"

你蹲下来，和CC一起看服务器上的指示灯。绿灯稳定地亮着，说明Echo的核心还在运转。

"Zero的核心防护网。"你说，"从猎杀者残骸里提取的数据显示，外围是一个树形结构。节点之间用最短路径通信。"

"树形？"CC问。

"对。像一棵倒着长的树——根在最上面，枝叶往下散。每个节点只和父节点、子节点通信。"

"那我们要做啥子？"

"找到最长的通信链路。"你说，"那就是Zero反应最慢的环节。"

你开始写。先把Zero的防护网建成一棵树，每个节点有权值。然后从任意一个节点出发，找到离它最远的节点A；再从A出发，找到离A最远的节点B。A到B的距离就是直径——最长的通信链路。

屏幕上跳出了结果。直径：47。

"又是47。"CC说。

"第47号节点。"Echo的声音从服务器里传出来，比往常轻，但语速没变，"那是Zero的次优通信路径。"

"次优？"你问。

"对。"Echo说，"最优路径已经被重重保护。但次优路径……是Zero的盲点。"

"那我们就从次优路径进去。"你说。

"不。"Echo说，"我们要在次优路径上，建一条更隐蔽的暗网。"

题目描述

$n$ 个节点，$m$ 条边的无向连通图。求严格次小生成树的权值和（即边权和严格大于最小生成树的最小生成树）。

输入格式

$n, m$。然后 $m$ 条边 $(u, v, w)$。

输出格式

严格次小生成树的边权和。

输入样例

3 2
1 2
2 3

输出样例

4557430888798830399

提示

• 先求MST，然后枚举非树边替换。
• 用LCA预处理树上路径的最大边和次大边。
• 时间复杂度 $O(m \log n)$。

"暗网建好了。"你说。

屏幕上出现了一张新的网——它和Zero的防护网重叠，但颜色更淡，几乎看不见。

"这就像……"CC想了想，"像寄生。我们长在Zero的皮肤下面。"

"对。"Echo说，"而且它不疼。"

CC第一次笑了——不是那种皮厚的笑，是真的笑了。

"走。"她说，"下一层。"

[第二题：追踪足迹]