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 <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

class UnionFind {
public:
	vector<int>par;

	void init(int size_) {
		par.resize(size_, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		par[u] = v;
	}
};

int N, M, A[50009], B[50009], C[50009], cnts, col[509];
vector<int>X[509]; vector<tuple<int, int, int>>tup, Z;

void dfs(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts;
	for (int i = 0; i < X[pos].size(); i++) dfs(X[pos][i]);
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i] >> C[i];
		tup.push_back(make_tuple(C[i], A[i], B[i]));
	}
	sort(tup.begin(), tup.end());

	int sum = 0; UnionFind UF; UF.init(N + 2);
	for (int i = 0; i < tup.size(); i++) {
		if (UF.same(get<1>(tup[i]), get<2>(tup[i])) == false) {
			UF.unite(get<1>(tup[i]), get<2>(tup[i]));
			Z.push_back(tup[i]);
		}
	}
	int ans = 0;
	for (int i = 0; i < Z.size(); i++) {
		for (int j = 1; j <= N; j++) { X[j].clear(); col[j] = 0; }
		for (int j = 0; j < Z.size(); j++) {
			if (i == j) continue;
			int to1 = get<1>(Z[j]), to2 = get<2>(Z[j]);
			X[to1].push_back(to2);
			X[to2].push_back(to1);
		}
		cnts++; dfs(get<1>(Z[i]));
		cnts++; dfs(get<2>(Z[i]));

		int cntu = 0;
		for (int j = 1; j <= M; j++) {
			if (col[A[j]] != col[B[j]] && get<0>(Z[i]) == C[j]) cntu++;
		}
		if (cntu == 1) { ans++; sum += get<0>(Z[i]); }
	}
	cout << ans << " " << sum << endl;
	return 0;
}