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 UnionFind{
	vector<int> data;
	UnionFind(int n) : data(n, -1){ }

	int find(int x){
		return data[x] < 0 ? x : data[x] = find(data[x]);
	}
	bool unite(int x, int y){
		x = find(x); y = find(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y){
		return find(x) == find(y);
	}
};

struct Edge{
	int src, dst, cst;
	Edge(int src, int dst, int cst) : src(src), dst(dst), cst(cst) { }
	bool operator==(const Edge &e)const{return src == e.src and dst == e.dst and cst == e.cst;}
	bool operator<(const Edge &e)const{return cst < e.cst;}
};

int N, M;

int kraskal(vector<Edge>& edges, vector<Edge>& tree, Edge rm){
	
	UnionFind uf(N);
	tree.clear();
	int ans = 0;
	
	for(auto e : edges){
		if(!(rm == e) && !uf.same(e.src, e.dst)){
			uf.unite(e.src, e.dst);
			ans += e.cst;
			tree.push_back(e);
		}
	}
	for(int i = 1; i < N; i++){
		if(!uf.same(0, i)){
			return 1e9;
		}
	}
	return ans;
}

vector<Edge> edges;
vector<Edge> tree;
vector<Edge> tmp;

int main(){
	cin >> N >> M;
	for(int i = 0; i < M; i++){
		int c,s,d;
		cin >> s >> d >> c;
		edges.push_back(Edge(s - 1, d - 1, c));
	}
	sort(edges.begin(), edges.end());
	int w = kraskal(edges, tree, Edge(-1, -1, -1));
	int ans = 0;
	int sum = 0;
	for(Edge e : tree){
		if(w < kraskal(edges, tmp, e)){
			ans++;
			sum += e.cst;
		}
	}
	cout << ans << " " << sum << endl;	
}