好的，我将题目中的数字和名称用 $...$ 标出。

题目描述

Farmer John 要把牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。
运输的总距离越小，运输成本越低。低成本的运输是 Farmer John 所希望的。
但他不想让竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。

运输方案可以看作是一棵生成树（连通所有销售点）。
你需要找到总距离第二小的生成树的距离。

注意：第二小生成树是指严格大于最小生成树总权值的最小总权值的生成树。

输入格式

第一行两个整数 $N,M$，表示顶点数和边数。
接下来 $M$ 行，每行三个整数 $x,y,z$，表示一条边的两端 $x,y$ 和距离 $z$。

输出格式

输出一个整数，表示第二小生成树的总距离。

数据范围

• $1 \le N \le 2000$
• $1 \le M \le 20000$
• $1 \le z \le 10^9$
• 数据可能有重边

输入样例

4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出样例

450

样例解释

图有 $4$ 个顶点 $4$ 条边：

1. $1-2$ : $100$
2. $2-4$ : $200$
3. $2-3$ : $250$
4. $3-4$ : $100$

最小生成树

边按权排序：$100,100,200,250$
用 Kruskal：

• 选 $(1,2,100)$
• 选 $(3,4,100)$
• 选 $(2,4,200)$，此时已连通 $1,2,3,4$
  总权值 $100+100+200=400$。

第二小生成树

考虑替换最小生成树中的一条边，使得总权值增加最少且大于 $400$。

最小生成树的边集：$(1,2,100), (3,4,100), (2,4,200)$
尝试替换：

• 替换 $(1,2,100)$：可用的非树边中连接 $1$ 和 $2$ 的最小边是 $100$（等于原边），不增加权值，不行；其他边 $(1,3)$ 不存在，$(1,4)$ 不存在。
• 替换 $(3,4,100)$：可用的非树边 $(2,3)=250$，去掉 $(3,4)$ 后，$3$ 通过 $2$ 连通？需要保证连通：去掉 $(3,4)$ 后，$3$ 与 $4$ 不连通，加入 $(2,3)=250$，则连通。新树权值 = $400 - 100 + 250 = 550$。
• 替换 $(2,4,200)$：可用的非树边 $(2,3)=250$，去掉 $(2,4)$ 后，$4$ 与 $2$ 不连通，加入 $(2,3)$ 后，$4$ 通过 $3$ 连通。新树权值 = $400 - 200 + 250 = 450$。

最小的严格大于 $400$ 的权值是 $450$。

输出 $450$。

这样题目就完整了，所有数字和名称都用 $...$ 标出。