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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"


struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

struct edge {
	int id;
	int to;
	int from;
	long long int time;
};
vector<edge>es;

int N, M;
pair<set<int>, long long int > getans(int banid) {
	UnionFind uf(N);
	long long int  cost = 0;
	set<int>aset;
	for (auto e : es) {
		if (uf.root(e.from) == uf.root(e.to))continue;
		if (e.id == banid)continue;
		else {
			uf.unionSet(e.from, e.to);
			cost += e.time;
			aset.emplace(e.id);
		}
	}
	if (uf.size(0) == N) {
		return make_pair(aset, cost);
	}
	else {
		return make_pair(aset, 2e12);
	}
}
int main() {cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int s, d, c; cin >> s >> d >> c; s--; d--;
		es.push_back(edge{ i,s,d,c });
	}
	sort(es.begin(), es.end(), [](const edge&l, const edge&r) {return l.time < r.time; });
	for (int i = 0; i < M; ++i) {
		es[i].id = i;
	}
	auto p(getans(-1));
	long long int mincost = p.second;
	vector<int>ans;
	long long int sum = 0;
	for (auto e : p.first) {
		if (getans(e).second != mincost) {
			ans.emplace_back(e); 
			sum += es[e].time;
		}
	}
	cout << ans.size() << " " << sum << endl;
	return 0;
}