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 <map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
class disjointset {
private:
	int sz;
	vector<int> par;
public:
	disjointset() : sz(0), par(vector<int>()) {};
	disjointset(int sz_) : sz(sz_) {
		par.resize(sz);
		for (int i = 0; i < sz; ++i) par[i] = i;
	}
	int root(int x) {
		if (x == par[x]) return x;
		return par[x] = root(par[x]);
	}
	void connect(int x, int y) {
		x = root(x);
		y = root(y);
		par[x] = y;
	}
};
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> A(M), B(M), C(M), perm(M);
	for (int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i] >> C[i]; --A[i], --B[i];
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) { return C[i] < C[j]; });
	map<int, vector<int> > g;
	for (int i = 0; i < M; ++i) {
		g[C[i]].push_back(i);
	}
	disjointset uf(N);
	vector<int> ans;
	for (pair<int, vector<int> > i : g) {
		vector<int> e = i.second;
		vector<vector<pair<int, int> > > gs(N);
		for (int j : e) {
			gs[uf.root(A[j])].push_back(make_pair(uf.root(B[j]), j));
			gs[uf.root(B[j])].push_back(make_pair(uf.root(A[j]), j));
		}
		vector<bool> vis(N);
		vector<int> eli;
		function<void(int)> dfs = [&](int pos) {
			vis[pos] = true;
			for (pair<int, int> j : gs[pos]) {
				if (vis[j.first]) continue;
				eli.push_back(j.second);
				dfs(j.first);
			}
		};
		for (int j = 0; j < N; ++j) {
			if (!vis[j]) dfs(j);
		}
		for (int j : eli) {
			disjointset uf2 = uf;
			for (int k = 0; k < N; ++k) {
				for (pair<int, int> l : gs[k]) {
					if (l.second != j) {
						uf2.connect(k, l.first);
					}
				}
			}
			if (uf2.root(A[j]) != uf2.root(B[j])) {
				ans.push_back(j);
			}
			uf.connect(A[j], B[j]);
		}
	}
	int sum = 0;
	for (int i : ans) sum += C[i];
	cout << ans.size() << ' ' << sum << endl;
	return 0;
}