RT hack数据也过不了 最后两个点TLE

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1,M=31;
const long long inf=LLONG_MAX>>1;
long long n,m,f[N],vis[N],sum=0,fa[N][M][3],tmp[10],p,dep[N];
struct data{
    int u,v,w,id;
}a[4*N];
struct node{
    int v,w,id;
};
vector<node>adj[N];
bool cmp(data x,data y)
{
    return x.w<y.w;
}
int ff(int x)
{
    if(f[x]==x)return x;
    else return f[x]=ff(f[x]);
}
void kruskal()
{
    for(register int i=1;i<=m;++i)
	{
        int u=a[i].u,v=a[i].v,w=a[i].w,id=a[i].id;
        if(ff(u)==ff(v))continue;
        f[ff(u)]=ff(v);
        sum+=w;
        vis[id]=1;
    }
}
void ft(long long a,long long b,long long c,long long d,long long x,long long y){
    tmp[1]=a;
    tmp[2]=b;
    tmp[3]=c;
    tmp[4]=d;
    tmp[5]=x;
    tmp[6]=y;
    sort(tmp+1,tmp+7);
    p=unique(tmp+1,tmp+7)-(tmp+1);
}
void dfs(int u,int lst)
{
    for(register int i=1;i<=20;++i)
	{
        fa[u][i][0]=fa[fa[u][i-1][0]][i-1][0];
        ft(fa[u][i-1][1],fa[u][i-1][2],fa[fa[u][i-1][0]][i-1][1],fa[fa[u][i-1][0]][i-1][2],0,0);
        fa[u][i][1]=tmp[p];
        fa[u][i][2]=tmp[p-1];
    }
    for(register int i=0;i<adj[u].size();++i)
	{
        int v=adj[u][i].v,w=adj[u][i].w,id=adj[u][i].id;
        if(v==lst||vis[id]==0)continue;
        dep[v]=dep[u]+1;
        fa[v][0][0]=u;
        fa[v][0][1]=w;
        fa[v][0][2]=0;
        dfs(v,u);
    }
}
pair<long long,long long> lca(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    long long m1=0,m2=0;
    for(register int i=20;i>=0;--i)
	{
        if(dep[fa[u][i][0]]>=dep[v])
		{
            ft(m1,m2,fa[u][i][1],fa[u][i][2],0,0);
            m1=tmp[p];
            m2=tmp[p-1];
            u=fa[u][i][0];
        }
    }
    if(u==v)return make_pair(m1,m2);
    for(register int i=20;i>=0;--i)
	{
        if(fa[u][i][0]!=fa[v][i][0])
		{
            ft(fa[u][i][1],fa[u][i][2],fa[v][i][1],fa[v][i][2],m1,m2);
            m1=tmp[p];
            m2=tmp[p-1];
            u=fa[u][i][0];
            v=fa[v][i][0];
        }
    }
    ft(fa[u][0][1],fa[u][0][2],fa[v][0][1],fa[v][0][2],m1,m2);
    m1=tmp[p];
    m2=tmp[p-1];
    return make_pair(m1,m2);
}
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)f[i]=i;
    for(register int i=1;i<=m;++i)
	{
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
        a[i].id=i;
        adj[a[i].u].push_back({a[i].v,a[i].w,i});
        adj[a[i].v].push_back({a[i].u,a[i].w,i});
    }
    sort(a+1,a+m+1,cmp);
    kruskal();
    dfs(1,0);
    long long ans=LLONG_MAX;
    for(register int i=1;i<=n;++i)
	{
        for(register int j=0;j<adj[i].size();++j)
		{
            int u=i,v=adj[i][j].v,w=adj[i][j].w,id=adj[i][j].id;
            if(vis[id])continue;
            pair<long long,long long> pll=lca(u,v);
            if(pll.first!=w)ans=min(ans,sum+w-pll.first);
            else ans=min(ans,sum+w-pll.second);
        }
    }
    cout<<ans;
}