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<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

/* --------------------------------------- */

ll n, m;
set<pair<ll, P>> edges;

class union_find {
public:
	union_find(int n)
	: par_(n, -1)
	{}
	void init(int n) {
		par_.assign(n, -1);
	}

	int root(int x) {
		return par_[x] < 0 ? x : par_[x] = root(par_[x]);
	}

	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if(x == y) {
			return false;
		} else {
			if(par_[x] < par_[y]) {
				par_[x] += par_[y];
				par_[y] = x;
			} else {
				par_[y] += par_[x];
				par_[x] = y;
			}
			return true;
		}
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	int size(int x) {
		return -par_[root(x)];
	}

private:
	std::vector<int> par_;
};

ll kruskal(vector<pair<ll, P>>& mst_edges) {
	union_find uf(n);
	ll ret = 0;
	for(auto edge: edges) {
		ll cost = edge.first;
		ll a = edge.second.first, b = edge.second.second;
		if(uf.same(a, b)) continue;
		uf.unite(a, b);
		ret += cost;
		mst_edges.pb(edge);
	}
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	REP(i, m) {
		ll s, d, c;
		cin >> s >> d >> c;
		s--; d--;
		edges.insert(make_pair(c, P(s, d)));
	}
	vector<pair<ll, P>> mst_edges;
	ll mst_cost = kruskal(mst_edges);
	ll ans1 = 0, ans2 = 0;
	REP(i, mst_edges.size()) {
		edges.erase(mst_edges[i]);
		vector<pair<ll, P>> tmp;
		ll cost = kruskal(tmp);
		if(cost > mst_cost || (ll)tmp.size() < n - 1) {
			ans1++;
			ans2 += mst_edges[i].first;
		}
		edges.insert(mst_edges[i]);
	}
	cout << ans1 << " " << ans2 << endl;
 	return 0;
}

/* --------------------------------------- */