树上倍增记录最小生成树上最大次大
的边。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ri register int
#define N 400005
#define M 900005
#define inf 0x2fffffffffffffff
struct node
{
int u, v, w, Next;
};
node e[M], A[M << 1];
bool B[M << 1];
int fa[N];
int first[N], tot = 0;
int n, m, bz[N][20], maxi[N][20], mini[N][20], deep[N];
inline bool cmp(node a, node b)
{
return a.w < b.w;
}
inline int getfa(int x)
{
if(x == fa[x])
{
return x;
}
return fa[x] = getfa(fa[x]);
}
inline void add(int x, int y, int z)
{
e[++tot].Next = first[x];
first[x] = tot;
e[tot].u = x;
e[tot].v = y;
e[tot].w = z;
return;
}
inline void dfs(int u, int fa)
{
bz[u][0] = fa;
for(ri i = first[u]; i; i = e[i].Next)
{
int v = e[i].v;
if(v == fa)
{
continue;
}
deep[v] = deep[u] + 1ll;
maxi[v][0] = e[i].w;
mini[v][0] = -inf;
dfs(v, u);
}
return;
}
inline void init()
{
for(ri i = 1; i <= 18; i++)
{
for(ri j = 1; j <= n; j++)
{
bz[j][i] = bz[bz[j][i - 1]][i - 1];
maxi[j][i] = max(maxi[j][i - 1], maxi[bz[j][i - 1]][i - 1]);
mini[j][i] = max(mini[j][i - 1], mini[bz[j][i - 1]][i - 1]);
if(maxi[j][i - 1] > maxi[bz[j][i - 1]][i - 1])
{
mini[j][i] = max(mini[j][i], maxi[bz[j][i - 1]][i - 1]);
}
else if(maxi[j][i - 1] < maxi[bz[j][i - 1]][i - 1])
{
mini[j][i] = max(mini[j][i], maxi[j][i - 1]);
}
}
}
return;
}
inline int lca(int x, int y)
{
if(deep[x] < deep[y])
{
swap(x, y);
}
for(ri i = 18; i >= 0; i--)
{
if(deep[bz[x][i]] >= deep[y])
{
x = bz[x][i];
}
}
if(x == y)
{
return x;
}
for(ri i = 18; i >= 0; i--)
{
if(bz[x][i] ^ bz[y][i])
{
x = bz[x][i];
y = bz[y][i];
}
}
return bz[x][0];
}
inline int qmax(int u, int v, int maxx)
{
int ans = -inf;
for(ri i = 18; i >= 0; i--)
{
if(deep[bz[u][i]] >= deep[v])
{
if(maxx != maxi[u][i])
{
ans = max(ans, maxi[u][i]);
}
else
{
ans = max(ans, mini[u][i]);
}
u = bz[u][i];
}
}
return ans;
}
signed main()
{
scanf("%lld%lld", &n, &m);
for(ri i = 1; i <= m; i++)
{
scanf("%lld%lld%lld", &A[i].u, &A[i].v, &A[i].w);
}
sort(A + 1, A + m + 1, cmp);
for(ri i = 1; i <= n; i++)
{
fa[i] = i;
}
int cnt = 0;
for(ri i = 1; i <= m; i++)
{
ri fx = getfa(A[i].u), fy = getfa(A[i].v);
if(fx == fy)
{
continue;
}
fa[fy] = fx;
cnt += A[i].w;
add(A[i].u, A[i].v, A[i].w);
add(A[i].v, A[i].u, A[i].w);
B[i] = true;
}
mini[1][0] = -inf;
deep[1] = 1;
dfs(1, 0);
init();
ri ans = inf;
for(ri i = 1; i <= m; i++)
{
if(!B[i])
{
ri lcf = lca(A[i].u, A[i].v), maxu = qmax(A[i].u, lcf, A[i].w), maxv = qmax(A[i].v, lcf, A[i].w);
ans = min(ans, cnt - max(maxu, maxv) + A[i].w);
}
}
printf("%lld", ans);
return 0;
}