记录编号	605431	评测结果	AAAAAAAAAA
题目名称	2453.次小生成树	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	0.407 s
提交时间	2025-09-01 10:51:37	内存使用	7.02 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const long long INF=2e9+5;

int n, m;
int fat[N], cnt, head[N];
struct edge { int u, v, w; } ed[N];
struct tree_edge { int v, w, nex; } e[N<<1];
bool cmp(edge x, edge y) { return x.w < y.w; }
int find(int x) { return fat[x] == x ? x : fat[x] = find(fat[x]); }
void addedge(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].nex = head[u];
    head[u] = cnt;
}

int dfn[N], son[N], siz[N], fa[N], top[N], num, deep[N];
int a[N], b[N];

struct tree_node { long long mx, cmx; } t[N<<2];

tree_node merge(tree_node x, tree_node y) {
    tree_node res;
    res.mx = max(x.mx, y.mx);
    if (x.mx == y.mx) {
        res.cmx = max(x.cmx, y.cmx);
    } else {
        if (x.mx > y.mx) {
            res.cmx = max(y.mx, x.cmx);
        } else {
            res.cmx = max(x.mx, y.cmx);
        }
    }
    return res;
}

void build(int p, int l, int r) {
    if (l == r) {
        t[p].mx = b[l];
        t[p].cmx = -INF;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    t[p] = merge(t[p<<1], t[p<<1|1]);
}

tree_node query_seg(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return t[p];
    int mid = (l + r) >> 1;
    if (R <= mid) return query_seg(p << 1, l, mid, L, R);
    if (L > mid) return query_seg(p << 1 | 1, mid + 1, r, L, R);
    return merge(query_seg(p << 1, l, mid, L, R), query_seg(p << 1 | 1, mid + 1, r, L, R));
}

void dfs1(int u, int f) {
    fa[u] = f;
    siz[u] = 1;
    deep[u] = deep[f] + 1;
    for (int i = head[u]; i; i = e[i].nex) {
        int v = e[i].v;
        if (v == f) continue;
        a[v] = e[i].w;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    dfn[u] = ++num;
    b[num] = a[u];
    top[u] = tp;
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (int i = head[u]; i; i = e[i].nex) {
        int v = e[i].v;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

tree_node ask_path(int x, int y) {
    tree_node res;
    res.mx = -INF;
    res.cmx = -INF;
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        tree_node tmp = query_seg(1, 1, n, dfn[top[x]], dfn[x]);
        res = merge(res, tmp);
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) swap(x, y);
    if (x != y) {
        tree_node tmp = query_seg(1, 1, n, dfn[x] + 1, dfn[y]);
        res = merge(res, tmp);
    }
    return res;
}

int tag[N];
long long minn;

int main() {
	freopen("secmst.in","r",stdin);
	freopen("secmst.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) fat[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);
    }
    sort(ed + 1, ed + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        int u = find(ed[i].u), v = find(ed[i].v);
        if (u == v) continue;
        fat[u] = v;
        minn += ed[i].w;
        tag[i] = 1;
        addedge(ed[i].u, ed[i].v, ed[i].w);
        addedge(ed[i].v, ed[i].u, ed[i].w);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    long long ans = 1e18;
    for (int i = 1; i <= m; i++) {
        if (tag[i]) continue;
        tree_node res = ask_path(ed[i].u, ed[i].v);
        if (res.mx == ed[i].w) {
            if (res.cmx != -INF) {
                ans = min(ans, minn - res.cmx + ed[i].w);
            }
        } else {
            ans = min(ans, minn - res.mx + ed[i].w);
        }
    }
    printf("%lld\n", ans);
    return 0;
}