次小生成树（LCA+库鲁斯卡尔）

思路：严格次小生成树，和最小生成树只有一条边他是不同的，那么利用这一点去写，我们先做最小生成树，然后把最小生成树用到的边建无向图,我们用d1[i][j]表示i点向上跳跃$2^j$个点的最大边权,d2同理表示次大边权，那么次小生成树肯定是用之前没有用的边去替换这里的最大边权或最小边权构成的，我们要替换旧边时，就是替换掉lca(a,b)中的d1,d2中的一个边。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int mod=100003;
const int N=1e5+5;
const int inf=0x7f7f7f7f;int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);
}ll lcm(ll a,ll b)
{return a*(b/gcd(a,b));
}template <class T>
void read(T &x)
{char c;bool op = 0;while(c = getchar(), c < '0' || c > '9')if(c == '-')op = 1;x = c - '0';while(c = getchar(), c >= '0' && c <= '9')x = x * 10 + c - '0';if(op)x = -x;
}
template <class T>
void write(T x)
{if(x < 0)x = -x, putchar('-');if(x >= 10)write(x / 10);putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{ll res=1%p;while(b){if(b&1)res=res*a%p;a=1ll*a*a%p;b>>=1;}return res;
}
struct node
{int a,b,w;bool used;bool operator < (const node &t)const{return w<t.w;}
}edge[N*6];int head[N*6],nex[N*6],to[N*6],w[N*6];
int n,m;
int tot;
int d1[N][17],d2[N][17],fa[N][17];
int dep[N];
int p[N];void add(int u,int v,int val)
{to[tot]=v;w[tot]=val;nex[tot]=head[u];head[u]=tot++;}
int fnd(int x)
{if(p[x]!=x) p[x]=fnd(p[x]);return p[x];
}
ll kruskal()
{for(int i=0;i<=n;i++ )p[i]=i;sort(edge,edge+m);ll res=0;for(int i=0;i<m;i++){int a=fnd(edge[i].a),b=fnd(edge[i].b),c=edge[i].w;if(a!=b){p[a]=b;res+=c;edge[i].used=true;}}return res;
}
void bfs()
{memset(dep,inf,sizeof dep);dep[0]=0,dep[1]=1;queue<int> q;q.push(1);while(q.size()){int u=q.front();q.pop();for(int i=head[u];~i;i=nex[i]){int v=to[i];if(dep[v]>dep[u]+1){dep[v]=dep[u]+1;q.push(v);fa[v][0]=u;d1[v][0]=w[i],d2[v][0]=-inf;for(int k=1;k<=16;k++){int root=fa[v][k-1];fa[v][k]=fa[root][k-1];int distance[4]={d1[v][k-1],d2[v][k-1],d1[root][k-1],d2[root][k-1]};d1[v][k]=d2[v][k]=-inf;for(int j=0;j<4;j++){int d=distance[j];if(d>d1[v][k]) d2[v][k]=d1[v][k],d1[v][k]=d;else if(d!=d1[v][k]&& d>d2[v][k]) d2[v][k]=d;}}}}}
}
void build()
{memset(head,-1,sizeof head);for(int i=0;i<m;i++){if(edge[i].used){int a=edge[i].a,b=edge[i].b,c=edge[i].w;add(a,b,c);add(b,a,c);}}}
int lca(int a,int b,int c)
{static int distance[N*2];int cnt=0;if(dep[a]<dep[b])swap(a,b);for(int k=16;k>=0;k--){if(dep[fa[a][k]]>=dep[b]){distance[cnt++]=d1[a][k];distance[cnt++]=d2[a][k];a=fa[a][k];}}if(a!=b){for(int k=16;k>=0;k--){if(fa[a][k]!=fa[b][k]){distance[cnt++]=d1[a][k];distance[cnt++]=d2[a][k];distance[cnt++]=d1[b][k];distance[cnt++]=d2[b][k];a=fa[a][k];b=fa[b][k];}distance[cnt++]=d1[a][0];distance[cnt++]=d1[b][0];}}int dist1=-inf,dist2=-inf;for(int i=0;i<cnt;i++){int d=distance[i];if(d>dist1) dist2=dist1,dist1=d;else if(d!=dist1&&d>dist2) dist2=d;}if(c>dist1)return c-dist1;if(c>dist2) return c-dist2;return inf;
}
int main()
{SIS;cin>>n>>m;for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;edge[i]={a,b,c};}ll sum=kruskal();build();bfs();ll res=1e18;for(int i=0;i<m;i++){if(!edge[i].used){int a=edge[i].a,b=edge[i].b,c=edge[i].w;res=min(res,sum+lca(a,b,c));}}cout<<res<<endl;return 0;}