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 <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
class UnionFind {
	mutable std::vector<int> vec;
public:
	UnionFind(const int size) : vec(size, -1) {};
	int find(int a) const {
		if (vec[a] < 0) return a;
		else return vec[a] = find(vec[a]);
	}
	bool same(int a, int b) const { return find(a) == find(b); }
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a != b) {
			if (vec[a] < vec[b]) {
				vec[a] += vec[b];
				vec[b] = a;
			}
			else {
				vec[b] += vec[a];
				vec[a] = b;
			}
		}
	}
	void clear() {
		std::fill(vec.begin(), vec.end(), -1);
	}
};
struct Bridge {
	int id, from, to, cost;
};
int main() {
	int n, m; std::cin >> n >> m;
	std::vector<Bridge> bridges(m); 
	for (auto i = 0; i < m; ++i){
		bridges[i].id = i;
		std::cin >> bridges[i].from >> bridges[i].to >> bridges[i].cost; --bridges[i].from, --bridges[i].to;
	}
	UnionFind uft(n);
	std::vector<bool> use_for_tree(bridges.size(), false);
	std::sort(bridges.begin(), bridges.end(), [](const Bridge& a, const Bridge& b) {return a.cost < b.cost; });
	int min_cost = 0;
	for (const auto b : bridges) {
		if (!uft.same(b.from, b.to)) {
			uft.unite(b.from, b.to);
			use_for_tree[b.id] = true;
			min_cost += b.cost;
		}
	}
	int alt_count = 0, alt_sum = 0;
	for (auto i = 0; i < bridges.size(); ++i) if (use_for_tree[bridges[i].id]) {
		uft.clear();
		int count = 0;
		int cost = 0;
		for (const auto b : bridges) if (b.id != bridges[i].id) {
			if (!uft.same(b.from, b.to)) {
				uft.unite(b.from, b.to);
				cost += b.cost;
				if (++count == bridges.size()) break;
			}
		}
		if (count != n - 1 || cost != min_cost) {
			++alt_count;
			alt_sum += bridges[i].cost;
		}
	}
	std::cout << alt_count << ' ' << alt_sum << '\n';
}