大致思路：找出最小生成树建图，然后遍历没用过的边看（比如没用过的边编号为$i$）$i$ 的起点和终点两点往上走（简单来说就是加的那一条边构成的环，消去除了那条边的环上任意一边得到的差值贡献中找最小正整数值）到最近公共祖先的边之中的第一大边和第二大边

（存第二大为防止第一大和要加的边权值相等而无法更新答案，若第二大和第一大等大且都等于加边边权则均无法更新答案）

因为题目说必有严格次小生成树，因此输出应该不用特判，求大佬帮看看九十分是怎么回事啊$QAQ$

（用了$vector$存图，配倍增查找，其中$b$数组第$i$ 个记录了恰好小于或等于$i$ 的$2^k$ 的$k$值）

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const ll maxn=1e5+10;
ll fa[31][maxn];
ll getfa(ll x){
   if(fa[0][x]!=x) fa[0][x]=getfa(fa[0][x]);
   return fa[0][x];
}
struct edge{
   ll st;
   ll ed;
   ll val;
}e[3*maxn];
bool cmp(edge a,edge b){
   return a.val<b.val;
}
vector<ll>v[maxn],val[maxn];
ll use[3*maxn],unuse[3*maxn];
bool p[maxn];
ll w[maxn];
ll maxv[31][maxn],smaxv[31][maxn];
ll dep[maxn];
ll maxdep=0;
void dfs(ll x,ll dept){
   maxdep=max(maxdep,dept);
   dep[x]=dept;
   p[x]=1;
   for(ll i=0;i<v[x].size();i++){
   	if(!p[v[x][i]]){
   		fa[0][v[x][i]]=x;
   		maxv[0][v[x][i]]=val[x][i];
   		smaxv[0][v[x][i]]=maxv[0][v[x][i]];
   		dfs(v[x][i],dept+1);
   	}
   }
}
ll b[maxn];
ll maxdif,smaxdif;
ll upload(ll x,ll dep,int r){
   ll times=dep,st=x,cl=0;
   while(times){
   	if(times&1){
   		st=fa[cl][st];
   		maxdif=max(maxdif,maxv[cl][st]);
   		if(smaxv[cl][st]!=r)smaxdif=max(smaxdif,smaxv[cl][st]);
   	}
   	cl++;
   	times>>=1;
   }
   return st;
}
ll upload2(ll x,ll dep){
   ll times=dep,st=x,cl=0;
   while(times){
   	if(times&1){
   		st=fa[cl][st];
   	}
   	cl++;
   	times>>=1;
   }
   return st;
}
void getdif(ll a,ll b1,int r){
   ll x=a,y=b1;
   if(dep[x]<dep[y])swap(x,y);
   x=upload(x,dep[x]-dep[y],r);
   for(ll i=b[dep[x]];i>=0;i--){
   	if(fa[i][x]!=fa[i][y]){
   		maxdif=max(maxdif,max(maxv[i][x],maxv[i][y]));
   		if(smaxv[i][x]!=r)smaxdif=max(smaxdif,smaxv[i][x]);
   		if(smaxv[i][y]!=r)smaxdif=max(smaxdif,smaxv[i][y]);
   		x=fa[i][x],y=fa[i][y];
   	}
   }
   maxdif=max(maxdif,max(maxv[0][x],maxv[0][y]));
   if(smaxv[0][x]!=r)smaxdif=max(smaxdif,smaxv[0][x]);
   if(smaxv[0][y]!=r)smaxdif=max(smaxdif,smaxv[0][y]);
   return ;
}
int main(){
   ll n,m,dif=0;
   cin>>n>>m;
   for(ll i=1;i<=n;i++){
   	fa[0][i]=i;
   }
   for(ll i=1;i<=m;i++){
   	cin>>e[i].st>>e[i].ed>>e[i].val;
   	dif+=e[i].val;
   }
   sort(e+1,e+1+m,cmp);
   ll cnt=0,rec=0,ans=0;
   while(cnt<n-1){
   	rec++;
   	ll now1=getfa(e[rec].st),now2=getfa(e[rec].ed);
   	if(now1!=now2){
   		ans+=e[rec].val;
   		cnt++;
   		use[++use[0]]=rec;
   		fa[0][now1]=now2;
   	}
   	else unuse[++unuse[0]]=rec;
   }
   while(rec<m){
   	unuse[++unuse[0]]=++rec;
   }
   for(ll i=1;i<=use[0];i++){
   	ll t1=e[use[i]].st,t2=e[use[i]].ed,t3=e[use[i]].val;
   	v[t1].push_back(t2);
   	v[t2].push_back(t1);
   	val[t1].push_back(t3);
   	val[t2].push_back(t3);
   }
   fa[0][1];
   dfs(1,1);
   ll ad=-1,base=1;
   for(ll i=1;i<=maxdep;i++){
   	if(i==base){
   		ad++;
   		base*=2;
   	}
   	b[i]=ad;
   }
   ad=1,base=2;
   while(base<=maxdep){
   	for(ll i=1;i<=n;i++){
   		fa[ad][i]=fa[ad-1][fa[ad-1][i]];
   		maxv[ad][i]=max(maxv[ad-1][i],maxv[ad-1][fa[ad-1][i]]);
   		if(maxv[ad-1][i]==maxv[ad-1][fa[ad-1][i]]){
   			smaxv[ad][i]=max(smaxv[ad-1][i],smaxv[ad-1][fa[ad-1][i]]);
   		}
   		else{
   			if(dep[i]<=base){
   				if(base/2>dep[i]-1) smaxv[ad][i]=smaxv[ad-1][i];
   				else smaxv[ad][i]=min(maxv[ad-1][i],maxv[ad-1][upload2(i,dep[i]-base/2-1)]);
   			}
   			else smaxv[ad][i]=min(maxv[ad-1][i],maxv[ad-1][fa[ad-1][i]]);
   		} 
   	}
   	ad++;
   	base*=2;
   }
   for(ll i=1;i<=unuse[0];i++){
   	maxdif=-1,smaxdif=-1;
   	getdif(e[unuse[i]].st,e[unuse[i]].ed,e[unuse[i]].val);
   	ll temp=e[unuse[i]].val;
   	if(temp>maxdif&&maxdif>-1)dif=min(dif,temp-maxdif);
   	else if(temp>smaxdif&&smaxdif>-1)dif=min(dif,temp-smaxdif);
   }
   cout<<ans+dif<<endl;
   return 0;
}