给定一张 N 个点 M 条边的无向图，求无向图的严格次小生成树。

设最小生成树的边权之和为 sum，严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。

输入格式
第一行包含两个整数 N 和 M。

接下来 M 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之前存在一条边，边的权值为 z。

输出格式
包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

数据范围
N≤105,M≤3×105

首先次小生成树与最小生成树只差一条边
先用kruskal求出最小生成树上的边，并记录下来用了哪条边和最小生成树的边权之和
然后建图，用bfs求每个点的深度并用树的最近公共祖先的倍增思想求出从每个点向上跳2^j次后到达的点和路径上的最大值和次大值；
枚举每条非树边将他们加入到最小生成树中，并用找最近公共祖先的方法求出从a到b的路径上的最大值和次大值
看看这条边的边权是否大于最大值或次大值即可;
时间复杂度m（logn）；

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=100010,M=300010,inf=0x3f3f3f3f;
ll n,m;
struct Edge
{
    ll a,b,w;
    ll used;
    bool operator <(const Edge &t)const
    {
        return w<t.w;
    }
}edge[M];   //存所有边; 
ll p[N];    //联通块; 
ll h[N],e[M],w[M],ne[M],idx;
ll depth[N],fa[N][17],d1[N][17],d2[N][17];
//depth表示为数的深度; fa[i][j]表示从此点开始向上走2^j步到哪个点
//d1[i][j]表示从i向上走2^j步的路径上的最大值，
//d2[i][j]表示从i向上走2^j步的路径上的次大值。
void add(ll a,ll b,ll c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
ll find(ll x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
long long kruskal()   //找到最小生成树; 
{
    for(ll i=1;i<=n;i++)p[i]=i; //初始化并查集; 
    sort(edge,edge+m);
    long long res=0;
    for(ll i=0;i<m;i++)
    {
        ll a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w;
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            edge[i].used=1;
        }
    }
    return res;
}
void build()   //建最小生成树的图
{
    memset(h,-1,sizeof(h));
    for(ll i=0;i<m;i++)
    {
        if(edge[i].used)
        {
            ll a=edge[i].a,b=edge[i].b,w=edge[i].w;
            add(a,b,w);add(b,a,w);
        }
     } 
}
void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    queue<ll>q;
    q.push(1);
    while(q.size())
    {
        ll t=q.front();
        q.pop();
        for(ll i=h[t];~i;i=ne[i])
        {
            ll j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;   //跳一次为t;
                d1[j][0]=w[i],d2[j][0]=-inf;  //初始化最大值最小值；
                for(ll k=1;k<=16;k++)
                {
                    ll anc=fa[j][k-1];
                    fa[j][k]=fa[anc][k-1];  //跳啊跳;
                    ll dist[4]={d1[j][k-1],d2[j][k-1],d1[anc][k-1],d2[anc][k-1]}; 
                    d1[j][k]=d2[j][k]=-inf;
                    for(ll u=0;u<4;u++)
                    {
                        ll d=dist[u];
                        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;
                    }
                } 
            }
        }
    }
}
ll lca(ll a,ll b,ll w)
{
    static ll dist[N*2];
    ll cnt=0;
    if(depth[a]<depth[b])swap(a,b);    //保证a在下面; 
    for(ll k=16;k>=0;k--)              //从大往小往上跳; 
        if(depth[fa[a][k]]>=depth[b])  //跳到同一层; 
        {
            dist[cnt++]=d1[a][k];    //把路径上的最大值和次小值记录下来； 
            dist[cnt++]=d2[a][k];     
            a=fa[a][k];          //跳过去; 
        }
    if(a!=b)
    {
        for(ll k=16;k>=0;k--)
            if(fa[a][k]!=fa[b][k])  //找到相等前的前一个点; 
            {
                dist[cnt++]=d1[a][k];  //记录路径上的最大值和次大值； 
                dist[cnt++]=d2[a][k];
                dist[cnt++]=d1[b][k];
                dist[cnt++]=d2[b][k];
                a=fa[a][k],b=fa[b][k];
            }
        dist[cnt++]=d1[a][0];  //记录跳到共同点时的最大值; 
        dist[cnt++]=d1[b][0];  //此时没有次大值; 
    }
    ll dist1=-inf,dist2=-inf;
    for(ll i=0;i<cnt;i++)   //找最大值和次大值; 
    {
        ll d=dist[i];
        if(d>dist1)dist2=dist1,dist1=d;
        else if(d!=dist1&&d>dist2)dist2=d;  
        //保证不等于最大值，因为为严格最大值; 
    }
    if(w>dist1)return w-dist1;
    if(w>dist2)return w-dist2;
    return inf;                //返回无穷; 
}
int main()
{
    cin>>n>>m;
    for(ll i=0;i<m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    long long sum=kruskal();
    build();
    bfs();
    long long res=1e18;     //long long范围的最大值;
    for(ll i=0;i<m;i++)    
        if(!edge[i].used)   //枚举每条非树边;
        {
            ll a=edge[i].a,b=edge[i].b,w=edge[i].w;
            res=min(res,sum+lca(a,b,w));
         } 
    cout<<res<<endl;
    return 0;
}