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 <bits/stdc++.h>
using namespace std;
const int maxn = 50010;
struct node
{
	int u,v,w;
	bool mark,del,use;
	node(int x = 0,int y = 0,int z = 0)
	{
		u = x;
		v = y;
		w = z;
		mark = del = use = false;
	}
	friend bool operator < (const node &a,const node &b)
	{
		return a.w < b.w;
	}
}e[maxn];

int uf[510],n,m,cnt;
bool flag[maxn];

int find(int x)
{
	return uf[x] = uf[x] == x?uf[x]:find(uf[x]);
}
void init()
{
	for(int i = 0;i <= n;i++) uf[i] = i;
}

int kruscal(bool &Unique,bool first)
{
	init();
	int ans,x,y;
	ans = 0;
	cnt = 0;
	for(int i = 0;i < m;i++)
	{
		if(!first && e[i].del) continue;
		x = find(e[i].u);
		y = find(e[i].v);
		if(x != y)
		{
			uf[x] = y;
			ans += e[i].w;
			if(first) 
		    {
			e[i].use = 1;
			if(e[i].mark) Unique = 0;
		    }
		    if(++cnt == n-1) return ans;
		}
		
		
	}
	return ans;
}


int main()
{
	//freopen("data.in","r",stdin);
	while(~scanf("%d %d",&n,&m))
	{
	int u,v,w,res1,res2;
	bool Unique = 1;
	memset(flag,0,sizeof(flag));
	for(int i = 0;i < m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		e[i] = node(u,v,w);
	}
	sort(e,e+m);
	for(int i = 1;i < m;i++)
	{
		if(e[i].w == e[i-1].w) e[i].mark = e[i-1].mark = 1;
	}
	int MST = kruscal(Unique,true);
	if(Unique) printf("%d %d\n",cnt,MST);
	else
	{
	res1 = 0,res2 = 0;
	for(int i = 0;i < m;i++)
	{
		if(e[i].mark && e[i].use)
		{
			e[i].del = 1;
	    	int mst = kruscal(Unique,false);
	    	if(mst == MST && cnt == n-1)
			flag[i] = 1;
	    	e[i].del = 0;
		}
	
		if(!flag[i] && e[i].use)
		{
			res1 ++;
			res2 += e[i].w;
		}
   } 
	printf("%d %d\n",res1,res2);	
}
}
}