树剖35pts求调可关

#include<bits/stdc++.h>
#define sdn cout
#define ll long long
#define vi vector<int>
#define ld double
#define vl vector<ll>
#define mpair make_pair
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
using namespace std;
mt19937_64 rnd(time(nullptr));
int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < 48 && ch > 57){
        if(ch == '-')  f = -1;
        ch = getchar();
    }
    while(ch >= 48 && ch <= 57){
        x  = x<<3 + x<<1 + ch-48;
        ch = getchar();
    }
    return x*f;
}
void write(int x){
    if(x < 0)  putchar('-'),x = -x;
    if(x > 9)  write(x/10);
    putchar(x%10+48);
}
const int N = 2e5 + 10,M = 1e6 + 10,INF1 = 1e9 + 7;
unsigned long long base1 = 131,base2 = 233317;
const ll INF2 = 1e18 + 7,Mod = 998244353;

int n,m,q,T,a[N],b[N],c[N],k,cnt,rt,f[N];
ll ans,sm;
struct node{
    int v,w;
};
struct edge{
    int u,v,w;
    bool operator <(const edge &p)const{
        return w < p.w;
    }
}e[M];
vector <node> lk[N];
struct sorahina{
    int f[N],bson[N],sz[N],tp[N],dfn[N],dep[N],id[N],cnt,mx[N<<2],ms[N<<2];
    void dfs1(int u,int fa){
        sz[u] = 1;dep[u] = dep[fa] + 1;
        for(auto k : lk[u]){
            if(k.v == fa)  continue;
            dfs1(k.v,u);
            sz[u] += sz[k.v];a[k.v] = k.w;
            if(sz[k.v] > sz[bson[u]])  bson[u] = k.v;
        }
    }
    void dfs2(int u,int fa,int top){
        tp[u] = top;dfn[u] = ++cnt;id[cnt] = u;
        if(bson[u])  dfs2(bson[u],u,top);
        for(auto k : lk[u]){
            if(k.v==fa || k.v==bson[u])  continue;
            dfs2(k.v,u,k.v);
        }
    }
    void pu(int p){
        if(mx[p<<1] > mx[p<<1|1]){
            mx[p] = mx[p<<1];
            ms[p] = max({ms[p<<1],ms[p<<1|1],mx[p<<1|1]});
        }
        else  if(mx[p<<1] < mx[p<<1|1]){
            mx[p] = mx[p<<1|1];
            ms[p] = max({ms[p<<1],ms[p<<1|1],mx[p<<1]});
        }
        else  mx[p] = mx[p<<1],ms[p] = max(ms[p<<1],ms[p<<1|1]);
    }
    void build(int p,int l,int r){
        if(l == r){
            mx[p] = a[id[l]];ms[p] = -INF1;
            return ;
        }
        int mid = l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
    }
    pii merge(pii a,pii b){
        pii res;
        if(a.first > b.first){
            res.first = a.first;
            res.second = max({a.second,b.second,b.first});
        }
        else  if(a.first < b.first){
            res.first = b.first;
            res.second = max({a.second,b.second,a.first});
        }
        else  res.first = a.first,res.second = max(a.second,b.second);
        return res;
    }
    pii qr(int n1,int n2,int l,int r,int p){
        if(n1 <= l && r <= n2)
          return {mx[p],ms[p]};
        pii res = {-INF1,-INF1};
        int mid = l+r>>1;
        if(n1 <= mid){
            pii t = qr(n1,n2,l,mid,p<<1);
            res = merge(res,t);
        }
        if(n2 > mid){
            pii t = qr(n1,n2,mid+1,r,p<<1|1);
            res = merge(res,t);
        }
        return res;
    }
    pii qry(int x,int y){
        pii res = {-INF1,-INF1};
        while(tp[x] != tp[y]){
            if(dep[tp[x]] < dep[tp[y]])  swap(x,y);
            pii t = qr(dfn[tp[x]],dfn[x],1,n,1);
            res = merge(res,t);
            x = f[tp[x]];
        }
        if(dep[x] > dep[y])  swap(x,y);
        if(x != y){
            pii t = qr(dfn[x]+1,dfn[y],1,n,1);
            res = merge(res,t);
        }
        return res;
    }
}tre;
int find(int x){
    if(f[x] != x)  f[x] = find(f[x]);
    return f[x];
}
void mg(int x,int y){
    int xx = find(x),yy = find(y);
    if(xx != yy)  f[xx] = yy;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i <= m;i ++){
        int u,v,w;cin>>u>>v>>w;
        e[i] = {u,v,w};
    }
    for(int i = 1;i <= n;i ++)  f[i] = i;
    sort(e+1,e+m+1);
    int x = 0,cnt = 1;
    while(x <= m && cnt < n){
        if(find(e[++x].u) != find(e[x].v)){
            mg(e[x].u,e[x].v);
            cnt ++;sm += e[x].w;
            b[x] = 1;
            lk[e[x].u].pb({e[x].v,e[x].w});
            lk[e[x].v].pb({e[x].u,e[x].w});
        }
    }
    a[1] = -INF1;
    tre.dfs1(1,0);tre.dfs2(1,0,1);
    tre.build(1,1,n);
    ans = INF2;
    for(int i = 1;i <= m;i ++){
        if(!b[i]){
            pair<int,int> res = tre.qry(e[i].u,e[i].v);
            if(e[i].w == res.first)  ans = min(ans,sm-res.second+e[i].w);
            else  ans = min(ans,sm-res.first+e[i].w);
        }
    }
    sdn<<ans<<endl;
    return 0;
}