Problem: Example

Input

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


Output

1 3

Solution (in CPP):

Solution:
// ACM-ICPCアジア地区予選2014 F. There is No Alternative

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int root[500];
int getRoot(int v){ return root[v]==-1 ? v : root[v] = getRoot(root[v]); }

int getMst(const vector<pair<int, pair<int, int> > >& vp, int N, int nouse){
	int cnt = 0, res = 0;
	memset(root, -1, sizeof(root));
	for(int i=0;i<vp.size();i++){
		if(i == nouse) continue;
		int p = getRoot(vp[i].second.first);
		int q = getRoot(vp[i].second.second);
		if(p != q){
			root[q] = p;
			cnt++;
			res += vp[i].first;
		}
	}
	if(cnt < N-1) return -1;
	return res;
}

int main(){
	int N, m;
	while(cin >> N >> m){
		vector< pair<int, pair<int, int> > > vp(m);
		for(int i=0;i<m;i++){
			cin >> vp[i].second.first >> vp[i].second.second >> vp[i].first;
			vp[i].second.first--;
			vp[i].second.second--;
		}
		sort(vp.begin(), vp.end());
		int minCost = 0;
		vector<int> idx;
		memset(root, -1, sizeof(root));
		for(int i=0;i<vp.size();i++){
			int p = getRoot(vp[i].second.first);
			int q = getRoot(vp[i].second.second);
			if(p != q){
				root[q] = p;
				minCost += vp[i].first;
				idx.push_back(i);
			}
		}
		int res = 0, sum = 0;
		for(int i=0;i<idx.size();i++){
			if(minCost != getMst(vp, N, idx[i])){
				res++;
				sum += vp[idx[i]].first;
			}
		}
		cout << res << " " << sum << endl;
	}
}