题意：求严格次小生成树（就是不能等于） 思路：先求一个最小生成树 枚举每条非树边 若连入则一定会成环

那么在这个环中 删去最大的边（除非树边） 就是一个次小生成树

但是如果那个最大边和非树边的值相等 有可能次小生成树的值就和最小生成树一样

显然是不成立的 所以应该记录一下次大值 最大值不满足就用次大值

注意：在dfs中转移的顺序

/*题意：求严格次小生成树（就是不能等于） 思路：先求一个最小生成树 枚举每条非树边 若连入则一定会成环那么在这个环中 删去最大的边（除非树边） 就是一个次小生成树但是如果那个最大边和非树边的值相等 有可能次小生成树的值就和最小生成树一样显然是不成立的 所以应该记录一下次大值 最大值不满足就用次大值注意：在dfs中转移的顺序 */#include
     
      using namespace std;#define N 100005#define ll long longstruct node{    int x,y,in; int w;}a[N*3];int fa[N],head[N<<1],nex[N<<1],to[N<<1],tot=0,f[N][22],dep[N];int d1[N][22],d2[N][22],w[N<<1],mn=0x7f7f7f;bool cmp(const node &a,const node &b) { return a.w
      
       =0;i--)    if(dep[f[x][i]]>=dep[y]) x=f[x][i];    if(x==y) return x;    for(int i=20;i>=0;i--)    if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];    return f[x][0];}//求路径的最大值和次大值 void solve(int x,int y,int v){    int mx1=0,mx2=0;    int t=dep[x]-dep[y];//深度差 是i的范围     for(int i=0;i<=20;i++)    if(t&(1<
       
        mx1) mx2=mx1,mx1=d1[x][i];        else mx2=max(mx2,d1[x][i]);        mx2=max(mx2,d2[x][i]);        x=f[x][i];    }    if(mx1!=v) mn=min(mn,v-mx1);    else mn=min(mn,v-mx2);}void work(int x,int y,int ww){    int lc=lca(x,y);     solve(x,lc,ww); solve(y,lc,ww);}ll ans=0;int main(){    int n,m,cnt=0;    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);    sort(a+1,a+1+m,cmp);    for(int i=1;i<=n;i++) fa[i]=i;    for(int i=1;i<=m;i++){        int f1=get(a[i].x),f2=get(a[i].y);        if(f1!=f2){            cnt++;            ans+=a[i].w;            a[i].in=1;            fa[f1]=f2;            add(a[i].x,a[i].y,a[i].w); add(a[i].y,a[i].x,a[i].w);        }        if(cnt==n-1) break;    }    dfs(1,0);    for(int i=1;i<=m;i++) if(!a[i].in) work(a[i].x,a[i].y,a[i].w);    printf("%lld\n",ans+mn);}/*5 61 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6 */