2nd Best Minimum Spanning Tree (MST)

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

#define siz 1000005

#define INF INT_MAX

typedef long long ll;

int N,E;

int p[siz],rank[siz];

vector <int> vec;



struct data{

    int u,v,c;

}a[siz];



void makeSet(int n){

    p[n]=n;

    rank[n]=0;

}



int findSet(int x){

    if(x!=p[x]) return p[x]=findSet(p[x]);

    return p[x];

}



void Union(int x, int y){

    if(rank[x]>rank[y]) p[y]=x;

    else{

        p[x]=y;

        if(rank[x]==rank[y]) rank[y]+=1;

    }

}



bool cmp(data a, data b){

    if(a.c<b.c) return true;

    return false;

}



ll findMST2(int n){

    ll mst2=0;

    int cnt=0;

    for(int i=0;i<=N;i++) makeSet(i);



    for(int i=0;i<E;i++){

        if(i!=n){

            if(findSet(a[i].u)!=findSet(a[i].v)){

                Union(findSet(a[i].u),findSet(a[i].v));

                mst2+=a[i].c;

                cnt++;

            }

        }

    }

    //cout<<cnt<<" "<<mst2<<" "<<N<<endl;

    if(cnt==N-1) return mst2;

    return -1;

}

int main()

{

    int u,v,c,n;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&N,&E);



        for(int i=0;i<=N;i++) makeSet(i);



        for(int i=0;i<E;i++){

            scanf("%d%d%d",&u,&v,&c);

            a[i].u=u;

            a[i].v=v;

            a[i].c=c;

        }



        sort(a,a+E,cmp);



        ll mst1=0;

        for(int i=0;i<E;i++){

            if(findSet(a[i].u)!=findSet(a[i].v)){

                Union(findSet(a[i].u),findSet(a[i].v));

                mst1+=a[i].c;

                vec.push_back(i);

            }

        }



        ll mst2=INF,val=0;

        for(int i=0;i<vec.size();i++){

            val=findMST2(vec[i]);

            //cout<<val<<endl;

            if(val!=-1) mst2=min(mst2,val);

        }

        if(mst2==INF) mst2=mst1;

        //cout<<mst1<<" "<<mst2<<endl;

        printf("%lld %lld\n",mst1,mst2);

        vec.clear();

    }

    return 0;

}