rt，貌似常数巨大，在 AcWing 上 Ofast+fread 才过

代码挺抽象的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int M=3e5+5;
const int INF=1e9;
const ll IINF=1e15;
template<typename T>void ckmax(T& x,T y){x=max(x,y);}
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<typename T>void read(T& x){
    x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
template<typename T,typename..._T>void read(T& x,_T&... y){read(x),read(y...);}
int n,m;
struct edge{int x,y,z,pre;}a[M*2];int alen,last[N];
void ins(int x,int y,int z=0){a[++alen]={x,y,z,last[x]};last[x]=alen;}
int fa[N];
void init(){for(int i=1;i<=n;i++)fa[i]=i;}
int getfa(int x){return fa[x]==x?x:getfa(fa[x]);}
void merge(int x,int y){fa[getfa(x)]=getfa(y);}
int e[M*2];
bool chs[M*2];
bool cmp(int x,int y){return a[x].z<a[y].z;}
ll Kruskal(){
    init();
    for(int i=2;i<=alen;i++)e[i]=i;
    sort(e+2,e+alen+1,cmp);
    ll ans=0;
    int cnt=0;
    for(int i=2;i<=alen;i++){
        int x=a[e[i]].x,y=a[e[i]].y;
        if(getfa(x)!=getfa(y)){
            merge(x,y);
            ans+=a[e[i]].z;
            chs[e[i]]=chs[e[i]^1]=1;
            if(++cnt==n-1)break;
        }
    }
    return ans;
}
int f[N][20],d[N],g[N][20][2];
void update(int x,int i){
    f[x][i]=f[f[x][i-1]][i-1];
    g[x][i][0]=max(g[x][i-1][0],g[f[x][i-1]][i-1][0]);
    g[x][i][1]=max(g[x][i-1][1],g[f[x][i-1]][i-1][1]);
    if(g[x][i-1][0]<g[f[x][i-1]][i-1][0])ckmax(g[x][i][1],g[x][i-1][0]);
    if(g[x][i-1][0]>g[f[x][i-1]][i-1][0])ckmax(g[x][i][1],g[f[x][i-1]][i-1][0]);
}
void dfs(int x,int fa,int v){
    d[x]=d[f[x][0]=fa]+1;
    g[x][0][0]=v,g[x][0][1]=-INF;
    for(int i=1;i<20&&f[x][i-1];i++)update(x,i);
    for(int k=last[x];k;k=a[k].pre){
        int y=a[k].y,z=a[k].z;
        if(chs[k]&&y!=fa)dfs(y,x,z);
    }
}
int mx[2];
void upd(int* val){
    for(int i=0;i<2;i++)
        if(val[i]>mx[0])mx[1]=mx[0],mx[0]=val[i];
        else if(val[i]<mx[0]&&val[i]>mx[1])mx[1]=val[i];
}
void LCA(int x,int y){
    mx[0]=mx[1]=-INF;
    if(x==y)return;
    if(d[x]<d[y])swap(x,y);
    for(int i=19;i>=0;i--)
        if(d[f[x][i]]>=d[y])
            upd(g[x][i]),
            x=f[x][i];
    if(x==y)return;
    for(int i=19;i>=0;i--)
        if(f[x][i]!=f[y][i])
            upd(g[x][i]),upd(g[y][i]),
            x=f[x][i],y=f[y][i];
    upd(g[x][0]),upd(g[y][0]);
}
int main(){
    read(n,m);
    alen=1;
    for(int i=1;i<=m;i++){
        int x,y,z;
        read(x,y,z);
        ins(x,y,z),ins(y,x,z);
    }
    ll sum=Kruskal(),ans=IINF;
    dfs(1,0,-INF);
    for(int i=2;i<=alen;i++)
        if(!chs[i]){
            int x=a[i].x,y=a[i].y,z=a[i].z;
            LCA(x,y);
            if(mx[0]<z)ckmin(ans,sum-mx[0]+z);
            else ckmin(ans,sum-mx[1]+z);
        }
    printf("%lld\n",ans);
    return 0;
}