记录编号	604993	评测结果	AAAAAAAAAA
题目名称	2453.次小生成树	最终得分	100
用户昵称	hsl_beat	是否通过	通过
代码语言	C++	运行时间	0.579 s
提交时间	2025-08-13 12:17:14	内存使用	20.04 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, cnt = 0;
struct edge
{
    int u, v, w;
}edges[1111111];
bool cmp(const edge &a, const edge &b)
{
    return a.w < b.w;
}
int head[111111], v[1111111], w[1111111], nxt[1111111], vis[1111111];
int dep[111111], fa[111111][25], a[111111][25], b[111111][25];
struct DSU
{
    int _n;
    vector<int> _fa, _size;
    explicit DSU(int __n) : _n(__n) {
        _fa.resize(_n + 1);
        _size.resize(_n + 1);
        for (int i = 1; i <= _n; i++) {
            _fa[i] = i;
            _size[i] = 1;
        }
    }
    int find(int _x) {
        if (_fa[_x] == _x) {
            return _x;
        }
        return _fa[_x] = find(_fa[_x]);
    }
    void merge(int _x, int _y) {
        assert(1 <= _x && _x <= _n);
        assert(1 <= _y && _y <= _n);
        _x = find(_x);
        _y = find(_y);
        if (_x == _y) {
            return;
        }
        _fa[_x] = _y;
        _size[_x] += _size[_y];
    }
    bool same(int _x, int _y) {
        assert(1 <= _x && _x <= _n);
        assert(1 <= _y && _y <= _n);
        _x = find(_x);
        _y = find(_y);
        return _x == _y;
    }
}dsu(0);
void add(int _u, int _v, int _w)
{
    nxt[++cnt] = head[_u];
    head[_u] = cnt;
    v[cnt] = _v;
    w[cnt] = _w;
}
int kruskal()
{
    int i;
    int ans = 0;
    sort(edges + 1, edges + m + 1, cmp);
    for (int i = 1; i <= m; ++i) {
        if (!dsu.same(edges[i].u, edges[i].v)) {
            vis[i] = 1;
            dsu.merge(edges[i].u, edges[i].v);
            ans += edges[i].w;
            add(edges[i].u, edges[i].v, edges[i].w);
            add(edges[i].v, edges[i].u, edges[i].w);
        }
    }
    return ans;
}
void dfs(int x)
{
    for (int i = head[x]; i; i = nxt[i]) {
        if (v[i] == fa[x][0]) {
            continue;
        }
        fa[v[i]][0] = x;
        dep[v[i]] = dep[x] + 1;
        a[v[i]][0] = w[i];
        b[v[i]][0] = 0;
        dfs(v[i]);
    }
}
int find(int u, int v, int k)
{
    int ans = 0;
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int i = 20; ~i; --i) {
        if (dep[fa[u][i]] >= dep[v]) {
            ans = max(ans, a[u][i] != k ? a[u][i] : b[u][i]);
            u = fa[u][i];
        }
    }
    if (u == v) {
        return ans;
    }
    for (int i = 20; ~i; --i) {
        if (fa[u][i] != fa[v][i]) {
            ans = max(ans, a[u][i] != k ? a[u][i] : b[u][i]);
            u = fa[u][i];
            ans = max(ans, a[v][i] != k ? a[v][i] : b[v][i]);
            v = fa[v][i];
        }
    }
    ans = max(ans, a[u][0] != k ? a[u][0] : b[u][0]);
    ans = max(ans, a[v][0] != k ? a[v][0] : b[v][0]);
    return ans;
}
signed main()
{
    freopen("secmst.in", "r", stdin);
    freopen("secmst.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    dsu = DSU(n + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    int x = kruskal();
    dep[1] = 1, dfs(1);
    for (int j = 1; j <= 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            a[i][j] = max(a[i][j - 1], a[fa[i][j - 1]][j - 1]);
            b[i][j] = max(b[i][j - 1], b[fa[i][j - 1]][j - 1]);
            if (a[i][j - 1] < a[fa[i][j - 1]][j - 1] && b[i][j] < a[i][j - 1]) {
                b[i][j] = a[i][j - 1];
            }
            if (a[i][j - 1] > a[fa[i][j - 1]][j - 1] && b[i][j] < a[fa[i][j - 1]][j - 1]) {
                b[i][j] = a[fa[i][j - 1]][j - 1];
            }
        }
    }
    int ans = LLONG_MAX;
    for (int i = 1; i <= m; ++i) {
        if (!vis[i]) {
            int tp = find(edges[i].u, edges[i].v, edges[i].w);
            if (tp != edges[i].w) {
                ans = min(ans, x - tp + edges[i].w);
            }
        }
    }
    cout << ans;
    return 0;
}