#include<bits/stdc++.h>
using namespace std;
#define int long long
struct edge{int to,w;};
struct Kruskal_edge{int u,v,w,num;}e[300005];
bool cmp(Kruskal_edge a,Kruskal_edge b){return a.w<b.w;}
struct segment_tree_node{int fi=0,se=0;};
bool bein_MST[300005];
int n,m,fa[100005],fa_on_tree[100005],dfn_cnt;
long long MST,second_ST=0x3f3f3f3f3f3f3f3f,val[100005],dfn[100005],rdfn[100005],dep[100005],siz[100005],wc[100005],top[100005];
segment_tree_node tree[400020];
vector<edge>t[100005];
//----------------------------------------------------------------------------------------------
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
void Kruskal(){
	int tmp=0;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++)	fa[i]=i;
	for(int i=1;i<=m;i++){
		int from=e[i].u,to=e[i].v;
		if(find(from)!=find(to)){
			merge(from,to);
			t[from].push_back({to,e[i].w});
			t[to].push_back({from,e[i].w});
			MST+=e[i].w;
			bein_MST[e[i].num]=1;
			tmp++;
			if(tmp==n-1)	return;
		}
	}
}//Kruskal
//----------------------------------------------------------------------------------------------
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
segment_tree_node merge(segment_tree_node a,segment_tree_node b){
	int s[4]={a.fi,a.se,b.fi,b.se};
	sort(s,s+4);
	int sz=unique(s,s+4)-s-1;
	return {s[sz],s[sz-1]};
}
void get_tree(int p,int l,int r){
	if(l==r){
		tree[p]={(int)val[rdfn[l]],-1};
		return;
	}
	int mid=(l+r)>>1;
	get_tree(ls(p),l,mid);
	get_tree(rs(p),mid+1,r);
	tree[p]=merge(tree[ls(p)],tree[rs(p)]);
}
segment_tree_node query(int p,int re_l,int re_r,int l,int r){
	if(re_l<=l&&re_r>=r)	return tree[p];
	else if(!(r<re_l||l>re_r)){
		int mid=(l+r)>>1;
		return merge(query(ls(p),re_l,re_r,l,mid),query(rs(p),re_l,re_r,mid+1,r));
	}
	return {-1,-1};
}
//Segment Tree
//----------------------------------------------------------------------------------------------
void dfs1(int now,int fa){
	dep[now]=dep[fa]+1;
	siz[now]=1;
	fa_on_tree[now]=fa;
	for(auto it:t[now]){
		int to=it.to,w=it.w;
		if(to!=fa){
			val[to]=w;
			dfs1(to,now);
			if(siz[to]>siz[wc[now]])	wc[now]=to;
			siz[now]+=siz[to];
		}
	}
}
void dfs2(int now,int fa,int Top){
	dfn[now]=++dfn_cnt;
	rdfn[dfn_cnt]=now;
	top[now]=Top;
	if(wc[now])	dfs2(wc[now],now,Top);
	for(auto it:t[now]){
		int to=it.to;
		if(to!=fa&&to!=wc[now])	dfs2(to,now,to);
	}
}
segment_tree_node qry(int x,int y){
	segment_tree_node tmp={-1,-1};
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		tmp=merge(tmp,query(1,dfn[top[x]],dfn[x],1,n));
		x=fa_on_tree[top[x]];
	}
	return merge(tmp,query(1,min(dfn[x],dfn[y])+1,max(dfn[x],dfn[y]),1,n));
}
//Tree chain partitioning
//----------------------------------------------------------------------------------------------
signed main(){
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		if(u!=v)	e[i]={u,v,w,i};
	}
	Kruskal();
	dfs1(1,0);
	dfs2(1,0,1);
	get_tree(1,1,n);
	int num=0;
	for(int i=1;i<=m;i++){
		if(!bein_MST[e[i].num]){
			segment_tree_node tmp=qry(e[i].u,e[i].v);
			//			cout<<num++<<" "<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<" "<<tmp.fi<<" "<<tmp.se<<"\n";
			if(tmp.fi!=e[i].w&&tmp.fi!=-1)	second_ST=min(second_ST,MST-tmp.fi+e[i].w);
			else if(tmp.se!=-1)	second_ST=min(second_ST,MST-tmp.se+e[i].w);
		}
	}
	cout<<second_ST;
}

AC on #3 #8