题目描述

给定一张 $\red {N}$ 个点 $\red {M }$条边的无向图，求无向图的严格次小生成树。

设最小生成树的边权之和为$\red {sum}$，严格次小生成树就是指边权之和大于$\red {sum}$的生成树中最小的一个。

输入格式

第一行包含两个整数$\red {N}$和$\red {M}$。

接下来$\red M$行，每行包含三个整数$\red {x，y，z}$，表示点$\red {x}$和点$\red {y}$之前存在一条边，边的权值为$\red {z}$。

输出格式

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

样例

输入样例

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

输出样例

11

提示

$\red {N≤10 ^5 ,M≤3\times 10^5}$