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;

#define for_(i,a,b) for(int i=a;i<b;++i)
#define allof(a) a.begin(),a.end()
#define size_of(a) (int)a.size()

// uniof-find
struct UnionFind {
private:
	vector< int > data;
	
public:
	UnionFind(int _size) : data(_size, -1) {}
	
	bool unionSet(int _x, int _y) {
		_x = root(_x); _y = root(_y);
		if (_x != _y) {
			if (data[_y] < data[_x]) swap(_x, _y);
			data[_x] += data[_y]; data[_y] = _x;
		}
		return _x != _y;
	}
	
	bool sameSet(int _x, int _y) { return root(_x) == root(_y); }
	
	int root(int _x) { return data[_x] < 0 ? _x : data[_x] = root(data[_x]); }
	
	int size(int _x) { return -data[root(_x)]; }
};

// minimum spanning tree --- with union-find
struct MST {
private:
	typedef int cost_type;
	
	struct MS_Edge {
		int from, to; cost_type cost; bool can, use;
		MS_Edge(int _from, int _to, cost_type _cost, bool _can, bool _use)
		 : from(_from), to(_to), cost(_cost), can(_can), use(_use) {}
		bool operator < (const MS_Edge& _a) const { return this->cost < _a.cost; }
	};
	
	int V;
	vector< MS_Edge > edges;
	
public:
	MST(int _n) : V(_n) {}
	
	void add_edge(int _from, int _to, cost_type _cost, bool can) {
		edges.push_back(MS_Edge(_from, _to, _cost, can, 0));
	}
	
	void solve() {		
		sort(allof(edges));
		
		int C = get_min_cost(1);
		
		int ans1 = 0, ans2 = 0;
		
		int e_size = size_of(edges);
		for_(i,0,e_size) {
			if (edges[i].use) {
				edges[i].can = false;
				
				int CC = get_min_cost(0);
				
				if (CC > C) {
					++ans1;
					ans2 += edges[i].cost;
				}
				
				edges[i].can = true;
			}
		}
		
		cout << ans1 << " " << ans2 << endl;
	}
	
	cost_type get_min_cost(bool f) {		
		UnionFind uf(V);
		cost_type res = cost_type();
		int e_size = size_of(edges), cnt = 0;
		
		for_(i,0,e_size) {
			MS_Edge &e = edges[i];
			if (e.can && !uf.sameSet(e.from, e.to)) {
				uf.unionSet(e.from, e.to);
				res += e.cost;
				if (f) e.use = true;
				++cnt;
			}
		}
		
		return cnt == V - 1 ? res : 1e9;
	}
};

int main() {
	int N, M; cin >> N >> M;

	MST mst(N);
	
	for_(i,0,M) {
		int a, b, c; cin >> a >> b >> c;
		--a; --b;
		mst.add_edge(a, b, c, 1);
	}
	
	mst.solve();
	
	return 0;
}