题意：求一棵树的严格次小生成树，即权值严格大于最小生成树且权值最小的生成树。
先求最小生成树，对于每个不在树中的边，取两点间路径的信息，如果这条边的权值等于路径中的权值最大值，那就删掉路径中的次大值，加上这条非树边，更新答案；否则删掉路径中的最大值，加上这条非树边，更新答案。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
struct edge{
int u,v,id;
ll w;
}e[];
int tot,go[],first[],next[];
ll val[];
int fa[][],deep[],F[],bin[],n,m;
ll mx1[][],mx2[][],ans1,ans2;
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll Read(){
char ch=getchar();ll t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
bool cmp(edge a,edge b){
return a.w<b.w;
}
void insert(int x,int y,ll z){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
val[tot]=z;
}
void add(int x,int y,int z){
insert(x,y,z);insert(y,x,z);
}
int find(int x){
if (F[x]==x) return x;
else return (find(F[x]));
}
void up(ll x,ll &y){
if (x>y) y=x;
}
void work(int x,int i){
mx1[x][i]=std::max(mx1[fa[x][i-]][i-],mx1[x][i-]);
if (mx1[fa[x][i-]][i-]<mx1[x][i]) up(mx1[fa[x][i-]][i-],mx2[x][i]);
if (mx1[x][i-]<mx1[x][i]) up(mx1[x][i-],mx2[x][i]);
up(mx2[x][i-],mx2[x][i]);
up(mx2[fa[x][i-]][i-],mx2[x][i]);
}
void dfs(int x,int f){
for (int i=;i<=;i++)
fa[x][i]=fa[fa[x][i-]][i-],work(x,i);
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==f) continue;
deep[pur]=deep[x]+;
fa[pur][]=x;
mx1[pur][]=val[i];
mx2[pur][]=;
dfs(pur,x);
}
}
void up(ll x,ll &a,ll &b){
if (x>a) b=a,a=x;
else
if (x>b&&x<a) b=x;
}
void lca(int x,int y){
ans1=,ans2=;
if (deep[x]<deep[y]) std::swap(x,y);
int t=deep[x]-deep[y];
for (int i=;i<=;i++)
if (t&bin[i]) {
up(mx1[x][i],ans1,ans2);
up(mx2[x][i],ans1,ans2);
x=fa[x][i];
}
for (int i=;i>=;i--)
if (fa[x][i]!=fa[y][i]) {
up(mx1[x][i],ans1,ans2);
up(mx2[x][i],ans1,ans2);
up(mx1[y][i],ans1,ans2);
up(mx2[y][i],ans1,ans2);
x=fa[x][i];
y=fa[y][i];
}
if (x!=y){
up(mx1[x][],ans1,ans2);
up(mx2[x][],ans1,ans2);
up(mx1[y][],ans1,ans2);
up(mx2[y][],ans1,ans2);
}
}
int main(){
bin[]=;
for (int i=;i<=;i++) bin[i]=bin[i-]*;
n=read();m=read();
for (int i=;i<=m;i++){
e[i].u=read();
e[i].v=read();
e[i].w=Read();
e[i].id=;
}
for (int i=;i<=n;i++)
for (int j=;j<=;j++)
mx1[i][j]=mx2[i][j]=;
std::sort(e+,e++m,cmp);
ll sum=;
for (int i=;i<=n;i++) F[i]=i;
for (int i=;i<=m;i++)
if (find(e[i].u)!=find(e[i].v)){
F[find(e[i].u)]=find(e[i].v);
e[i].id=;
add(e[i].u,e[i].v,e[i].w);
sum+=e[i].w;
}
dfs(,);
ll Ans=10000000000000000LL;
for (int i=;i<=m;i++)
if (!e[i].id){
lca(e[i].u,e[i].v);
if (e[i].w==ans1) Ans=std::min(Ans,sum-ans2+e[i].w);
else Ans=std::min(Ans,sum-ans1+e[i].w);
}
printf("%lld\n",Ans);
}