次小生成树

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m;
typedef long long int LL;
struct edge{
    int a, b, w;
    bool isu;
    bool operator<(const edge& e) const 
    {
        return w < e.w;
    }
} e[M];

int p[N];
int dist1[N][N], dist2[N][N];

int h[N], ele[M * 2], ne[M * 2], we[M * 2], idx;

void add(int a, int b, int w)
{
    ele[idx] = b, we[idx] = w ,ne[idx] = h[a], h[a] = idx ++; 
}

int find(int a)
{
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
    d1[u] = maxd1;
    d2[u] = maxd2;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = ele[i];
        int w = we[i];
        if (j != fa)
        {
            int td1 = maxd1, td2 = maxd2;
            if (w > td1) td2 = td1, td1 = w;
            else if (w < td1 && w > td2) td2 = w;
            dfs(j, u, td1, td2, d1, d2);
        }
    }
}

int main(void)
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i ++)
        cin >> e[i].a >> e[i].b >> e[i].w;
    sort(e, e + m);
    for (int i = 1; i <= n; i ++)   p[i] = i;

    LL sum = 0;
    for (int i = 0; i < m; i ++)
    {
        int a = e[i].a, b = e[i].b;
        int pa = find(e[i].a), pb = find(e[i].b), w = e[i].w;
        if (pa != pb)
        {
            p[pa] = pb;
            sum += w;
            add(a, b, w), add(b, a, w);
            e[i].isu = true;
        }
    }

    for (int i = 1; i <= n; i ++)
        dfs(i, -1, 0, 0,dist1[i], dist2[i]);

    LL res = 1e18;
    for (int i = 0; i < m; i ++)
    {
        if (!e[i].isu)
        {
            int a = e[i].a, b = e[i].b, w = e[i].w;
            if (w > dist1[a][b])
                res = min(res, sum  - dist1[a][b] + w);
            else if (w > dist2[a][b])
                 res = min(res, sum  - dist2[a][b] + w);
        }
    }
    cout << res << endl;
    return 0;
}