几个月前写的，今天甚至有点看不懂我自己的代码了……

#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 2000005
#define maxm 10000005
typedef ull long long;
struct node
{
    ull x, y;
    ull z;
    bool operator<(const node& rhs)const
    {
        return z < rhs.z;
    }
}xyz[maxm];
struct edge
{
    ull to,next;
    ull len;
}e[maxn];
ull p[maxn],eid,f[maxn][20],d[maxn],fa[maxn],n,m,num=0,q[maxm];
ull sum=0,g[2][maxn][20],ans=0x7fffffffffffffff;
ull get(ull x)
{
    if (fa[x] == x)
    {
        return x;
    }
    fa[x] = get(fa[x]);
    return fa[x];
}
bool merge(ull x, ull y)
{
    x = get(x);
    y = get(y);
    if (x != y)
    {
        fa[y] = x;
        return true;
    }
    return false;
}
void addedge(ull u,ull v,ull w)
{
    e[++eid].to=v;
    e[eid].next=p[u];
    e[eid].len=w;
    p[u]=eid;
}
void dfs(ull u)
{
    d[u]=d[f[u][0]]+1;
    for(ull i=p[u];i!=0;i=e[i].next)
    {
        ull v=e[i].to;
        if(v==f[u][0])
        {
            continue;
        }
        f[v][0]=u;
        g[0][v][0]=e[i].len;
        dfs(v);
    }
}
ull lca(ull a)
{
    ull x=xyz[a].x;
    ull y=xyz[a].y;
    if(d[x]<d[y])
    {
        swap(x,y);
    }
    ull k=0;
    while((1<<(k+1))<=d[x])
    {
        k++;
    }
    ull res1=0,res2=0;
    for(ull i=k;i>=0;i--)
    {
        if(d[f[x][i]]>=d[y])
        {
            if(g[0][x][i]>res1)
            {
                res1=g[0][x][i];
                if(g[1][x][i]<res1)
                {
                    res2=max(res2,g[1][x][i]);
                }
            }
            else
            {
                if(g[0][x][i]<res1)
                {
                    res2=max(res2,g[0][x][i]);
                } 
                else
                {
                    if(g[1][x][i]<res1)
                    {
                        res2=max(res2,g[1][x][i]);
                    }
                }
            }
            x=f[x][i];
        }
    }
    if(x!=y)
    {
        for(ull i=k;i>=0;i--)
        {
            if(f[x][i]!=f[y][i])
            {
                if(g[0][x][i]>res1)
                {
                    res1=g[0][x][i];
                    if(g[1][x][i]<res1)
                    {
                        res2=max(res2,g[1][x][i]);
                    }
                }
                else
                {
                    if(g[0][x][i]<res1)
                    {
                        res2=max(res2,g[0][x][i]);
                    } 
                    else
                    {
                        if(g[1][x][i]<res1)
                        {
                            res2=max(res2,g[1][x][i]);
                        }
                    }
                }
                if(g[0][y][i]>res1)
                {
                    res1=g[0][y][i];
                    if(g[1][y][i]<res1)
                    {
                        res2=max(res2,g[1][y][i]);
                    }
                }
                else
                {
                    if(g[0][y][i]<res1)
                    {
                        res2=max(res2,g[0][y][i]);
                    } 
                    else
                    {
                        if(g[1][y][i]<res1)
                        {
                            res2=max(res2,g[1][y][i]);
                        }
                    }
                }
                x=f[x][i];
                y=f[y][i];
            }
        }
    }
    if(g[0][x][0]>res1)
    {
        res1=g[0][x][0];
        if(g[1][x][0]<res1)
        {
            res2=max(res2,g[1][x][0]);
        }
    }
    else
    {
        if(g[0][x][0]<res1)
        {
            res2=max(res2,g[0][x][0]);
        } 
        else
        {
            if(g[1][x][0]<res1)
            {
                res2=max(res2,g[1][x][0]);
            }
        }
    }
    if(g[0][y][0]>res1)
    {
        res1=g[0][y][0];
        if(g[1][y][0]<res1)
        {
            res2=max(res2,g[1][y][0]);
        }
    }
    else
    {
        if(g[0][y][0]<res1)
        {
            res2=max(res2,g[0][y][0]);
        } 
        else
        {
            if(g[1][y][0]<res1)
            {
                res2=max(res2,g[1][y][0]);
            }
        }
    }
    if(res1!=xyz[a].z)
    {
        return res1;
    }
    return res2;
}
int main()
{
    cin >> n >> m;
    for(ull i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for (ull i = 1; i <= m; i++)
    {
        cin >> xyz[i].x >> xyz[i].y >> xyz[i].z;
        if(xyz[i].x==xyz[i].y){
            xyz[i].x=xyz[i].y=xyz[i].z=0;
            i--;
            m--;
        }
    }
    sort(xyz + 1, xyz + m + 1);
    for (ull i = 1; i <= m; i++)
    {
        if (merge(xyz[i].x, xyz[i].y))
        {
            num++;
            sum+=xyz[i].z;
            addedge(xyz[i].x,xyz[i].y,xyz[i].z);
            addedge(xyz[i].y,xyz[i].x,xyz[i].z);
        }
        else
        {
            q[0]++;
            q[q[0]]=i;
        }
    }
    dfs(1);
    for(ull i=1;(1<<i)<=n;i++)
    {
        for(ull j=1;j<=n;j++)
        {
            f[j][i]=f[f[j][i-1]][i-1];
            g[0][j][i]=max(g[0][j][i-1],g[0][f[j][i-1]][i-1]);
            if(g[0][j][i]!=g[0][j][i-1])
            {
                g[1][j][i]=max(g[1][j][i],g[0][j][i-1]);
            }
            if(g[0][j][i]!=g[0][f[j][i-1]][i-1])
            {
                g[1][j][i]=max(g[1][j][i],g[0][f[j][i-1]][i-1]);
            }
            if(g[0][j][i]!=g[1][j][i-1])
            {
                g[1][j][i]=max(g[1][j][i],g[1][j][i-1]);
            }
            if(g[0][j][i]!=g[1][f[j][i-1]][i-1])
            {
                g[1][j][i]=max(g[1][j][i],g[1][f[j][i-1]][i-1]);
            }
        }
    }
    for(ull i=1;i<=m-n+1;i++)
    {
        ull w1=xyz[q[i]].z;
        ull w2=lca(q[i]);
        ans=min(ans,sum-w2+w1);
    }
    cout<<ans;
    return 0;
}