题目描述

求最小生成树已经难不倒你了。

那么次小生成树呢？

N 个点，编号为 1 ~ N。M 条无向边。可能有自环，可能有重边。

求次小生成树的边权和。

注：次小生成树的边权和肯定大于最小生成树的边权和。

输入格式

第一行：两个整数 $N$, $M$

接下来 $M$ 行：每行三个整数 $u, v, w$ 表示点 $u$ 和点 $v$ 之间有一条权值为 $w$ 的无向边。

输出格式

一个整数，表示次小生成树的边权和。

样例输入

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

样例输出

11

提示

$50\%$ 的数据， $N\le 2000$，$M\le 3000$。

$80\%$ 的数据， $N\le 5\times 10^4$，$M\le 10^5$。

$100\%$ 的数据， $N\le 10^5$，$M\le 3\times10^5$，$0 \le w \le 10^9$，数据保证有解。