Problem: Example

Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3


Output

1 3

Solution (in CPP):

Solution:
#include<iostream>
#include<algorithm>
using namespace std;

int P[510];
int cost1[100100],src1[100100],dst1[100100],judge[100100],mark[100100];

void init(int N)
{
	for (int i=0; i<=N; ++i) 
	    P[i] = i;
} 

int root(int a)
{
	if(P[a]==a)   
	   return a;
	else  return(P[a]=root(P[a]));
}
 
bool is_same_set(int a,int b)
{
	return(root(a)==root(b));
}

void unite(int a,int b)
{
	P[root(a)]=root(b);
}

int Kruskal(int cost[101000],int src[101000],int dst[101000],int n,int M,int h) 
{
	pair<int,int> edges[101000];
	for(int i=0;i<M;i++)
	{
		edges[i].first=cost[i];
		edges[i].second=i;
	}
	sort(edges,edges+M);
	int sum=0;
	int k=0;
	for(int i=0;i<M;i++)
	{
		if(is_same_set(src[edges[i].second],dst[edges[i].second])||edges[i].first>10000)
		  continue;
		unite(src[edges[i].second],dst[edges[i].second]);
		if(h)
		{
			src1[k]=src[edges[i].second];
		    dst1[k]=dst[edges[i].second];
		    cost1[k]=edges[i].first;
		    mark[k]=edges[i].second;
		    k++;
		}
		sum+=edges[i].first;
	}
	int flag=1;
	for(int i=2;i<=n;i++)
	{
		if(!is_same_set(1,i))
		{
			flag=0;
			break;
		}
	}
	if(!flag)
	   sum=-1; 
	return sum;
}

int main()
{
	int n,m;
    cin >> n >> m;
    if(!n && !m)
      return 0;
        init(n);
	    int cost[101000],src[101000],dst[101000];
	    for(int i=0;i<m;i++)
	    {
            cin >> src[i] >> dst[i] >> cost[i];
            src1[i]=0;
            dst1[i]=0;
            cost1[i]=0;
            judge[i]=0;
            mark[i]=0;
		}
 	    int sum=Kruskal(cost,src,dst,n,m,1);
 	    /*cout << sum << endl; */
 	    for(int i=0;i<n-1;i++)
 	    {
 	    	int k=mark[i];
 	    	cost[k]=10001;
 	    	init(n);
 	    	/*for(int j=k;j<m;j++)
 	    	{
 	    		cost[j]=cost[j+1];
 	    		src[j]=src[j+1];
 	    		dst[j]=dst[j+1];
			}*/
			int sum1;
 	    	sum1=Kruskal(cost,src,dst,n,m,0);
 	    	/*cout << sum1 << endl;  */
 	    	if(sum!=sum1)
 	    	  judge[i]=1;
 	    	cost[k]= cost1[i];
 	    	/*for(int j=k+1;j<m;j++)
 	    	{
 	    		cost[j]=cost[j-1];
 	    		src[j]=src[j-1];
 	    		dst[j]=dst[j-1];
			}
			cost[k]=cost1[i];
			src[k]=src1[i];
			dst[k]=dst1[i];*/
		}
		int count=0,money=0;
		for(int i=0;i<n-1;i++)
		{
			if(judge[i])
			{
				count++;
				money+=cost1[i];
			}
		}
		cout << count << ' ' << money << endl;
}