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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	bool operator<(const struct Info &arg) const{
		return cost < arg.cost;
	};
	int from,to,cost;
};

int* parent,*height;
int N,M;

int getParent(int id){
	if(parent[id] == id)return id;
	else{
		return parent[id] = getParent(parent[id]);
	}
}

bool isSame(int a, int b){
	return getParent(a) == getParent(b);
}

void unite(int a,int b){
	int a_parent = getParent(a);
	int b_parent = getParent(b);

	if(a_parent == b_parent)return;

	if(height[a_parent] > height[b_parent]){
		parent[b_parent] = a_parent;
	}else{
		if(height[a_parent] == height[b_parent])height[b_parent]++;
		parent[a_parent] = b_parent;
	}
}

void init_array(){
	for(int i = 0; i < N; i++){
		parent[i] = i;
		height[i] = 0;
	}
}


int main(){

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

	parent = new int[N];
	height = new int[N];

	init_array();

	Info* info = (Info*)malloc(sizeof(Info)*M);

	for(int i = 0; i < M; i++){
		scanf("%d %d %d",&info[i].from,&info[i].to,&info[i].cost);
		info[i].from--;
		info[i].to--;
	}

	int minimum = 0;

	sort(info,info+M);

	vector<int> V;

	for(int i = 0; i < M; i++){
		if(!isSame(info[i].from,info[i].to)){
			unite(info[i].from,info[i].to);
			V.push_back(i);
			minimum += info[i].cost;
		}
	}

	int tmp_cost,group_num,check_id,ans = 0,num = 0;

	for(int loop = 0; loop < V.size();loop++){
		check_id = V[loop];

		init_array();

		tmp_cost = 0;

		for(int i = 0; i < M; i++){
			if(isSame(info[i].from,info[i].to) == false && i != check_id){
				unite(info[i].from,info[i].to);
				tmp_cost += info[i].cost;
			}
		}

		if(tmp_cost > minimum){
			ans += info[check_id].cost;
			num++;
			continue;
		}

		group_num = 0;
		for(int i = 0; i < N; i++){
			if(parent[i] == i)group_num++;
		}

		if(group_num > 1){
			ans += info[check_id].cost;
			num++;
			continue;
		}

	}

	printf("%d %d\n",num,ans);

	return 0;
}