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 {
	int		size;
	int		*par;
	int		*rank;
	UnionFind(int size): size(size), par(NULL), rank(NULL) {
		assert(size > 0);
		par = new int[size];
		rank = new int[size];
		assert(par != NULL && rank != NULL);
		for (int i = 0; i < size; ++i) {
			par[i] = i;
			rank[i] = 0;
		}
	}
	~UnionFind() {
		delete [] par;
		delete [] rank;
		par = NULL;
		rank = NULL;
	}
	int		find(int idx) {
		if (par[idx] == idx)
			return idx;
		return (par[idx] = find(par[idx]));
	}
	bool	same(int lhs, int rhs) {
		if (find(lhs) == find(rhs))
			return true;
		return false;
	}
	void	unite(int lhs, int rhs) {
		int	par_l = find(lhs), par_r = find(rhs);
		if (par_l == par_r)
			return;
		if (rank[par_l] < rank[par_r]) {
			par[par_l] = par_r;
		} else {
			par[par_r] = par_l;
			if (rank[par_l] == rank[par_r])
				++rank[par_l];
		}
	}
};

using III = tuple<int, int, int>;
using Graph = vector<vector<int>>;

vector<int>	calc_reachable(int N, const Graph &graph, int src, int dst)
{
	vector<int>		reachable_vec;
	vector<bool>	seen(N, false);
	stack<int>		stck;
	stck.push(src);
	seen.at(src) = true;
	reachable_vec.push_back(src);
	while (!stck.empty()) {
		int u = stck.top(); stck.pop();
		for (int v : graph.at(u)) {
			if (seen.at(v) || (u == src && v == dst))
				continue;
			seen.at(v) = true;
			reachable_vec.push_back(v);
			stck.push(v);
		}
	}
	return reachable_vec;
}

int	main()
{
	int	N, M;
	cin >> N >> M;
	int	S, D, C;
	vector<III>	edge(M);
	int	cost[500][500] = {};
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j)
			cost[i][j] = -1;
	}
	for (int i = 0; i < M; ++i) {
		cin >> S >> D >> C;
		--S; --D;
		edge.at(i) = make_tuple(C, S, D);
		cost[S][D] = C;
		cost[D][S] = C;
	}
	sort(edge.begin(), edge.end());
	UnionFind	uf(N);
	Graph		graph(N);	
	for (int i = 0; i < M; ++i) {
		tie(C, S, D) = edge.at(i);
		if (uf.same(S, D))
			continue;
		uf.unite(S, D);
		graph.at(S).push_back(D);
		graph.at(D).push_back(S);
	}
	int	total = 0, cnt = 0;
	for (int u = 0; u < N; ++u) {
		for (int v : graph.at(u)) {
			if (u >= v)
				continue;
			vector<int>	reachable_u = calc_reachable(N, graph, u, v);
			vector<int> reachable_v = calc_reachable(N, graph, v, u);
			bool		is_altanative = false;
			for (int u2 : reachable_u) {
				for (int v2 : reachable_v) {
					if (u2 == v2 || (u == u2 && v == v2))
						continue;
					if (cost[u][v] == cost[u2][v2]) {
						is_altanative = true;
						break;
					}
				}
				if (is_altanative)
					break;
			}
			if (!is_altanative) {
				++cnt;
				total += cost[u][v];
			}
		}
	}
	cout << cnt << " " << total << endl;
}