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 <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
using namespace std;

using Weight = int;
struct Edge {
	int src, dst, id; Weight weight;
	Edge() {}
	Edge(int s, int d, int id, Weight w) : src(s), dst(d), id(id), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

struct UnionFind {
	vector<int> par;
	int cnt;
	UnionFind(int size_) : par(size_, -1), cnt(size_) {}
	void unite(int x, int y) {
		if((x = find(x)) != (y = find(y))) {
			if(par[y] < par[x]) swap(x, y);
			par[x] += par[y]; par[y] = x; cnt--;
		}
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
	int size(int x) { return -par[find(x)]; }
	int size() { return cnt; }
};

int N, M;
bool operator < (const Edge &e, const Edge &f) { return e.weight < f.weight; }
pair<Weight, Edges> kruskal(Edges es) {
	UnionFind uf(N);
	Weight total = 0; Edges T;
	for(auto &e : es)if(!uf.same(e.src, e.dst)) {
		T.push_back(e); total += e.weight; uf.unite(e.src, e.dst);
	}
	return make_pair(total, T);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while(cin >> N >> M) {
		vector<Edge> es(M);
		for(int i = 0; i < M; i++) {
			int a, b, w;
			cin >> a >> b >> w;
			a--, b--;
			es[i] = Edge(a, b, i, w);
		}
		sort(es.begin(), es.end());

		int req = 0, total = 0;
		auto res = kruskal(es);
		for(Edge& e : res.second) {
			Edges es2;
			for(int i = 0; i < M; i++) {
				if(es[i].id == e.id) continue;
				es2.push_back(es[i]);
			}
			auto res2 = kruskal(es2);
			if(res2.second.size() != N - 1 || res.first < res2.first) {
				req++;
				total += e.weight;
			}
		}

		cout << req << " " << total << endl;
	}
}