题目描述

Bestcc为了这场宴会已经准备了很久，他邀请了很多人。

Bestcc已花重金买下一个有$n$个房间，为了玩游戏，且以无向的连廊，游戏规则如下：

· 每个房间都藏了一个人

· 通过每两个房间之间的通道都会耗费体力

· 抓的人要消耗最少的体力抓到所有人

· 抓的人有一次机会让两个不直接相连的房间变得相连（这条道不耗费体力），也可以不用

. 抓的人可自选从哪个房间开抓

---

在以上规则中求最省体力抓完所有人的方案（通道可以来回走）

输入格式

第一行2个数，$n$表示房间的个数，$m$表示通道的条数

接下来的m行，每行三个数$u$，$v$，$w$，表示$u$房间与$v$房间之间有一条通道，走这条通道要花费$w$点体力

输出格式

一个数，表示花费最小的体力

样例 #1

样例输入 #1

4 3
1 2 10
1 3 3
2 4 1

样例输出 #1

4

样例 #2

样例输入 #2

5 6
1 2 4
2 3 2
1 4 7
4 5 3
2 4 2
3 5 5

样例输出 #2

9

提示

提示

$1≤n≤20000$

样例解释:

先选起点在2房间抓到第一个人， 从2到4房间花1点体力抓到第二个人，再从4使用机会到3花0点体力抓到第三个人，然后从3到1花3点体力抓到最后一个人，游戏结束

样例解释2： 可得最小体力为9