# 修桥笑传之坚决不用第一版方案

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB

## 背景故事

浮岛之间要修桥，工程师刚交上一份总造价最低的设计图，验收员就在封面盖了个大章：“第一版方案，坚决不用！”

工程师问：“那我换几座桥，凑出一份同样便宜的图呢？”验收员摇头：“价格没变，只能算第一版换了个封面。”于是工程师只好寻找一份能连通所有浮岛、总造价**严格高于**最低值的方案。既然已经被迫多花钱，他们至少想让这笔额外开销尽可能小。

(本故事由GPT-6 Sol重写)

## 形式化问题描述

给定一个含 $n$ 个顶点、$m$ 条带正整数权值的无向边的连通图。顶点编号为 $1$ 到 $n$ ；允许重边，不含自环。一个方案是原图的一棵生成树，造价是树上所有边权之和。令 $W_{\min}$ 为所有生成树的最小造价。

求所有造价严格大于 $W_{\min}$ 的生成树中的最小造价。保证这样的生成树存在。即使有多棵最小生成树，它们的造价仍等于 $W_{\min}$ ，不算答案。

## 输入格式

第一行两个整数 $n,m$ .

接下来 $m$ 行，每行三个整数 $u,v,w$ ，表示一条连接 $u$ 与 $v$ 、边权（造价）为 $w$ 的无向边。重边作为不同的候选边。

## 输出格式

输出一个整数，表示所求的最小造价。

## 样例 1

### 输入

```text
3 5
1 2 3
1 2 5
2 3 4
2 3 9
1 3 3
```

### 输出

```text
7
```

### 解释

最低造价为 $3+3=6$ . 选择权值为 $3$ 的边 $(1,3)$ 与权值为 $4$ 的边 $(2,3)$ ，得到严格更高的最小造价 $7$ .

## 样例 2

### 输入

```text
3 4
1 2 1
2 3 1
1 3 1
1 2 3
```

### 输出

```text
4
```

### 解释

前三条边中任选两条都得到造价为 $2$ 的最小生成树。使用最后一条边得到的最小造价是 $4$ ；造价为 $3$ 的生成树不存在。

## 数据范围与保证

- $2\le n\le 100\,000$ .
- $n\le m\le 200\,000$ .
- $1\le w\le 5\,000$ .
- $1\le u,v\le n$ 且 $u\ne v$ .
- 图连通，并且至少存在一棵造价严格大于 $W_{\min}$ 的生成树。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 20% | $n\le 10$ ，$m\le 20$ |
| 30% | $n\le 5\,000$ ，$m\le 10\,000$ |
| 50% | 无额外条件 |