Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005, M = 300005, K = 17, inf = 0x3f3f3f3f;
struct Edge{
    int a, b, c;
    bool tree;
}edge[M];
int f[N], dep[N], fa[N][K], d1[N][K], d2[N][K];
struct EDGE{
    int e, to, nxt;
}g[N << 1];
int h[N], idx, n, m;
bool cmp(Edge A,Edge B)
{
    return A.c < B.c;
}
int find(int x)
{
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}
void add(int a,int b,int c)
{
    g[++idx] = {c, b, h[a]}, h[a] = idx;
}
long long Kruskal()
{
    sort(edge + 1, edge + m + 1, cmp);
    for (int i=1;i<=n;i++)
        f[i] = i;
    long long sum = 0;
    for (int i=1;i<=m;i++)
    {
        int x = find(edge[i].a), y = find(edge[i].b);
        if (x != y)
        {
            f[x] = y;
            edge[i].tree = true;
            sum += edge[i].c;
            add(edge[i].a, edge[i].b, edge[i].c);
            add(edge[i].b, edge[i].a, edge[i].c);
        }
    }
    return sum;
}
void dfs(int u,int father)
{
    for (int i = h[u]; i; i = g[i].nxt)
    {
        int j = g[i].to;
        if (j == father)
            continue;
        dep[j] = dep[u] + 1;
        fa[j][0] = u;
        d1[j][0] = g[i].e;
        d2[j][0] = -inf;
        for (int k=1;k<K;k++)
        {
            int f0 = fa[j][k - 1];
            fa[j][k] = fa[f0][k - 1];
            const int dis[4] = {d1[j][k - 1], d2[j][k - 1], d1[f0][k - 1], d2[f0][k - 1]};
            d1[j][k] = d2[j][k] = -inf;
            for (int l=0;l<4;l++)
            {
                int d = dis[l];
                if (d > d1[j][k])
                {
                    d2[j][k] = d1[j][k];
                    d1[j][k] = d;
                }
                else if (d != d1[j][k] && d > d2[j][k])
                    d2[j][k] = d;
            }
        }
        dfs(j, u);
    }
}
int lca(int a,int b,int c)
{
    static int dis[200];
    int cnt = 0;
    if (dep[a] < dep[b])
        swap(a, b);
    for (int i=16;i>=0;i--)
        if (dep[fa[a][i]] >= dep[b])
        {
            dis[cnt ++] = d1[a][i];
            dis[cnt ++] = d2[a][i];
            a = fa[a][i];
        }
    if (a != b)
    {
        for (int i=16;i>=0;i--)
            if (fa[a][i] != fa[b][i])
            {
                dis[cnt ++] = d1[a][i];
                dis[cnt ++] = d2[a][i];
                dis[cnt ++] = d1[b][i];
                dis[cnt ++] = d2[b][i];
                a = fa[a][i];
                b = fa[b][i];
            }
    }
    int dis1 = -inf, dis2 = -inf;
    for (int i=0;i<cnt;i++)
    {
        int d = dis[i];
        if (d > dis1)
        {
            dis2 = dis1;
            dis1 = d;
        }
        else if (d != dis1 && d > dis2)
            dis2 = d;
    }
    if (c > dis1)
        return c - dis1;
    if (c > dis2)
        return c - dis2;
    return inf;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].c);
    long long sum = Kruskal();
    dep[1] = 1;
    dfs(1, 0);
    long long ans = 9e18;
    for (int i=1;i<=m;i++)
        if (!edge[i].tree)
            ans = min(ans, sum + lca(edge[i].a, edge[i].b, edge[i].c));
    printf("%lld", ans);
    return 0;
}