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;
struct Line{
	int id,x,y,z;
};
int n,m;
Line l[50010];
int ls[510],f[510],cnt,anss,ansc,mint;
int min(int a,int b){
	return a<b?a:b;
}
int F(int z){
	if(f[z]!=z)f[z]=F(f[z]);
	return f[z];
}
void init_f(){
	for(int i=0;i<=n;i++)
		f[i]=i;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		l[i].id=i;
		scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].z);
	}
	sort(l, l + m, [](Line a, Line b){ return a.z < b.z; });
	init_f();
	cnt=0,mint=0;
	for(int p=0;cnt<n-1;){
		for(;F(l[p].x)==F(l[p].y);p++);
		mint+=l[p].z;
		f[F(l[p].x)]=F(l[p].y);
		ls[cnt++]=p;
	}
	for(int i=0;i<n-1;i++){
		init_f();
		int t=0,p=0;
		for(cnt=0;cnt<n-1;){
			for(;(p<m)&&(p==ls[i]||F(l[p].x)==F(l[p].y));p++);
			if(p==m){
				t=mint+1;
				break;
			}
			t+=l[p].z;
			f[F(l[p].x)]=F(l[p].y);
			cnt++;
		}
		if(mint<t){
			anss++;
			ansc+=l[ls[i]].z;
		}
	}
	printf("%d %d\n",anss,ansc);
}