倍增（LCA）+最小生成树
施工队挖断学校光缆导致断网1天（大雾）
考虑直接枚举不在最小生成树上的边。但是边权可能与最小生成树上的边相等，这样删边时权值不改变，就不满足条件了
所以我们可以先用倍增处理出最小生成树上任意2点之间的最大边权和次大边权
枚举每条不在最小生成树上的边，接到树上，再删去最大边（与枚举边的边权不等）或次大边（最大边与枚举边的边权相等），做个判断
判断边（u，v）时 我们只要询问（u，lca）和（v，lca）就可以了
找了半个多小时才发现数组不够大....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
template <typename T> inline T max(T &a,T &b) {return a>b ?a:b;}
template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;}
template <typename T> inline void read(T &x){
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
}
struct edge{int from,to,dis;}a[];
int n,m,cnt,f[],hd[],nxt[],ed[],poi[],val[]; //邻接表存边
bool vis[];
inline bool cmp(const edge &A,const edge &B) {return A.dis<B.dis;}
inline int find(int x) {return f[x]==x ? x:f[x]=find(f[x]);}
inline void add(int x,int y,int v){
nxt[ed[x]]=++cnt; hd[x]=hd[x] ? hd[x]:cnt;
ed[x]=cnt; poi[cnt]=y; val[cnt]=v;
} struct LCA{
int d[],fa[][],fir[][],sec[][]; //fir:最大值 sec:次大值
inline void dfs(int x,int _fa){ //dfs预处理
d[x]=d[_fa]+; fa[x][]=_fa;
for(int i=;(<<i)<=d[x];++i){
fa[x][i]=fa[fa[x][i-]][i-];
fir[x][i]=max(fir[x][i-],fir[fa[x][i-]][i-]);
if(fir[x][i]!=fir[fa[x][i-]][i-]) sec[x][i]=max(sec[x][i],fir[fa[x][i-]][i-]); //次大值
else if(fir[x][i]!=fir[x][i-]) sec[x][i]=max(sec[x][i],fir[x][i-]);
}
for(int i=hd[x];i;i=nxt[i])
if(poi[i]!=_fa){
fir[poi[i]][]=val[i];
sec[poi[i]][]=-1e9-;
dfs(poi[i],x);
}
}
inline int lca(int x,int y){ //最近公共祖先
if(d[x]<d[y]) swap(x,y);
for(int i=;i>=;--i)
if(d[x]-(<<i)>=d[y])
x=fa[x][i];
if(x==y) return x;
for(int i=;i>=;--i)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][];
}
inline int query(int x,int y,int k){ //询问（x,y）之间的最大值
int res=-1e9-;
for(int i=;i>=;--i)
if(d[fa[x][i]]>=d[y]){
if(fir[x][i]!=k) res=max(res,fir[x][i]);
else res=max(res,sec[x][i]);
x=fa[x][i];
}
return res;
}
}mo1;
int main(){
read(n); read(m);
for(int i=;i<=n;++i) f[i]=i;
for(int i=;i<=m;++i) read(a[i].from),read(a[i].to),read(a[i].dis);
sort(a+,a+m+,cmp); int k=; long long tot=,ans=1e16;
for(int i=;i<=m&&k<n-;++i){
int r1=find(a[i].from),r2=find(a[i].to);
if(r1!=r2){
tot+=a[i].dis; f[r1]=r2; vis[i]=; ++k;
add(a[i].from,a[i].to,a[i].dis);
add(a[i].to,a[i].from,a[i].dis);
}
}mo1.dfs(,);
for(int i=;i<=m;++i){
if(vis[i]) continue; //在最小生成树上
int _lca=mo1.lca(a[i].from,a[i].to);
int q1=mo1.query(a[i].from,_lca,a[i].dis); //询问(u,lca)
int q2=mo1.query(a[i].to,_lca,a[i].dis); //询问(v,lca)
ans=min(ans,tot-max(q1,q2)+(long long)a[i].dis); //换边找最小值
}printf("%lld",ans);
return ;
}