非严格次小生成树

题目描述

给一张1~n个节点编号的m条边的图，生成一个非严格次小生成树。

非严格次小生成树指的是树的边权之和在大于等于最小生成树的所有边权之和情况下，最小的权值总和。

输入

输入第一行包含两个正整数n,m

接着输入m行，每行3个数字u,v,w。表示u和v之间有一条权值w的边

输出

非严格次小生成树的边权之和

样例

提示

2 < n \leq 10^5, n \leq m \leq 10^ 6, 0 < w \leq 10^9

u_i \not = v_i

保证输入至少能生成两棵不同的树

来源

模板