rt 我使用的算法是树剖+线段树求严格次小边
对拍了几组答案，发现我的答案会比标答小，比mst大

#include <iostream>
#include <algorithm>
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (s+((t-s)>>1))
#define int long long
#define mp (make_pair)
#define pii pair<int, int>
using namespace std;
const int maxn=1e6;
int ffa[maxn],fa[maxn],son[maxn],sz[maxn],de[maxn],tp[maxn],dfn[maxn],va[maxn],hd[maxn],cst[maxn];
int sztree,cntnode;
int n, m,u,v,vale,cnt,num,ecnt;
bool vis[maxn];
pair<int, int> sumv[maxn];
struct node1{
	int from, to, val;
	bool operator < (const node1 b) const{
		return val < b.val;
	}
}edge[maxn];
struct node2{
	int to, nex, val;
}e[maxn];
inline void adde(int from, int to, int val)
{
	e[++cnt] = node2{to, hd[from], val};
	hd[from] = cnt;
}
inline int find(int x) { return x==ffa[x] ? x : ffa[x]=find(ffa[x]);}
inline void merge(int x, int y)
{
	x=find(x), y=find(y);
	ffa[x] = y;
}
void mst()
{
	sort(edge+1, edge+1+m);
	for (int i=1; i<=m; i++)
	{
		u = edge[i].from, v=edge[i].to, vale=edge[i].val;
		if (find(u) == find (v)) continue;
		vis[i] = true;	
		merge(u, v);
		sztree += vale;
		adde(u,v,vale),adde(v,u,vale);
		if (++cntnode == n-1) break;
	}
}

inline void dfs1(int nw, int en)
{
	fa[nw] = en;
	sz[nw] = 1;
	de[nw] = de[en] + 1;
	for (int i=hd[nw]; i; i=e[i].nex)
	{
		if (e[i].to==en)
			continue;
		va[e[i].to] = e[i].val;
		dfs1(e[i].to, nw);
		sz[nw] += sz[e[i].to];
		if (sz[e[i].to] > sz[son[nw]])
			son[nw] = e[i].to;
	}
}

inline void dfs2(int nw, int en)
{
	tp[nw] = en;
	dfn[nw] = ++num;
	cst[num] = va[nw];
	if (son[nw]) dfs2(son[nw], en);
	for (int i=hd[nw]; i; i=e[i].nex)
	{
		if (e[i].to==fa[nw] || e[i].to == son[nw])
			continue;
		dfs2(e[i].to, e[i].to);
	}
}

inline pii getmax(pii x, pii y)
{
	pii ss;
	if (x.first == y.first){
		ss.first=x.first;
		ss.second=max(x.second, y.second);
	}
	else 
	{
		ss.first=max(x.first, y.first);
		ss.second=max(min(x.first, y.first), max(x.second, y.second));
	}
	return ss;
}

inline void push_up(int o)
{
	sumv[o] = getmax(sumv[ls], sumv[rs]);
}

inline void build(int o, int s, int t)
{
	if (s==t) {
		sumv[o].first = cst[s];
		return ;
	}
	build(ls, s, mid);
	build(rs, mid+1, t);
	push_up(o);
}

inline pii query(int o, int l, int r, int s, int t)
{
	if (l<=s && r>=t){
		return sumv[o];
	}
	pii ss(0,0);
	if (l <= mid) ss=getmax(ss, query(ls, l, r, s, mid));
	if (r > mid)  ss=getmax(ss, query(rs, l, r, mid+1, t));
	return ss;
}

inline pii lca(int a, int b)
{
	pii ss(0,0);
	while (tp[a] != tp[b])
	{
		if (de[tp[a]] < de[tp[b]])
			swap(a,b);
		ss=getmax(ss, query(1, dfn[tp[a]], dfn[a], 1, n));
		a=fa[tp[a]];
	}
	if (de[a] > de[b])	
		swap(a, b);
	ss=getmax(ss, query(1, dfn[a], dfn[b], 1, n));
	return ss;
} 

void init()
{
	mst();
	dfs1(1, 0);
	dfs2(1, 1);
	build(1, 1, n);
}

signed main()
{
	//freopen("C://Users//19637//Downloads//tree4.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> n >> m ;
	for (int i=1; i<=m; i++)
	{
		ffa[i] = i;
		cin >> u >> v >> vale;
		if (u==v) continue;
		edge[++ecnt] = {u, v, vale};
	}
	m = ecnt;
	init();
	int dea=1e16;
	for (int i=1; i<=m; i++)
	{
		if (vis[i]) continue;
		u=edge[i].from, v=edge[i].to, vale=edge[i].val;
		pii ss=lca(u, v);
		if (vale == ss.first && ss.second)
			dea=min(dea, vale-ss.second);
		else 
			dea=min(dea, vale-ss.first);
		//if(dea==21) cout << u << "---------------" << v << endl;
	}
	//cout << "mst=" <<  sztree << endl;
	cout << sztree+dea;
	return 0;

}