UVA 10600 - ACM Contest and Blackout (First Minimum spanning tree AND Second Minimum spanning tree)

First Minimum spanning tree
Second Minimum spanning tree


2
5 8        ///5 holo node 8 holo edge
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

OUTPUT :110 121

9 14     ///9 holo node 14 holo edge
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10


Output 37 37


///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define sz 103
#define inf 1<<29
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
struct edge
{
    int f,t,c;
    edge(int a,int b,int co)
    {
        f=a;
        t=b;
        c=co;
    }
};

vector<edge>vec;
int n,e,ans2,edgetaken[sz],etl;
int comp(edge a,edge b)
{
    return a.c<b.c;
}
int par[sz];
int set_find(int a)
{
    if(a==par[a])
        return a;
    return(par[a]=set_find(par[a]));
}
void link(int x,int y)
{
    if(x>y)
        par[x]=y;
    else par[y]=x;
}
int  mst(void)
{
    int i=0,j,x,y,sum=0,cnt=0;
    etl=0;
    sort(vec.begin(),vec.end(),comp);
    for(i=0; i<e && cnt<n-1; i++)
    {
        x=set_find(vec[i].f);
        y=set_find(vec[i].t);

        if(x!=y)
        {
            link(x,y);
            sum+=vec[i].c;
            edgetaken[etl++]=i;
            cnt++;
        }
    }
    return sum;
}
void ini(void)
{
    for(int i=1; i<=n; i++)
        par[i]=i;
}

int main()
{
//   freopen("in.txt","r",stdin);

    int t,i,j,f,c,tst,cs,cnt,ans1,an2,x,y,miin;
    scanf("%d",&tst);
    for(cs=1; cs<=tst; cs++)
    {
        scanf("%d %d",&n,&e);
        ini();
        vec.clear();
        memset(edgetaken,0,sizeof edgetaken);
        for(j=0; j<e; j++)
        {
            scanf("%d %d %d",&f,&t,&c);
            vec.push_back(edge(f,t,c));
        }

        ans1=mst();

        //2nd mst
        miin= inf;
        for(i=0; i<etl; i++)
        {
            ini();
            cnt=0;
            ans2=0;
            for(j=0; j<e && cnt<n-1; j++)
            {
                //     printf("i %d j %d\n",i,j);
                if(edgetaken[i]!=j)
                {
                    x=set_find(vec[j].f);
                    y=set_find(vec[j].t);
                    //       printf("f %d t %d c %d\n",vec[j].f,vec[j].t,vec[j].c);
                    if(x!=y)
                    {
                        cnt++;
                        link(x,y);
                        ans2+=vec[j].c;
                    }
                }
            }
            //   printf("ans %d\n",ans2);
            if(cnt==n-1 && miin>ans2)
                miin=ans2;
        }
        printf("%d %d\n",ans1,miin);
    }
    return 0;
}