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 Edge
{
	int a, b;
	double cost;

	Edge () {}
	Edge (int a, int b, double cost) : a(a), b(b), cost(cost) {}

	bool operator < (const Edge &d) const
	{
		return ( cost < d.cost );
	}
};

struct Unionfind
{
	vector < int > par;

	Unionfind(int n)
	{
		par = vector < int >(n);
		for ( int i = 0; i < n; i++ ) {
			par[i] = i;
		}
	}

	void unite(int x, int y)
	{
		x = root(x), y = root(y);
		if ( x == y ) return;
		par[x] = y;
	}

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

	int root(int n)
	{
		return par[n] = (par[n] == n ? n : root(par[n]));
	}
};

int main()
{
	int N, M;
	Edge edges[50005];
	vector < int > selected;

	cin >> N >> M;
	for ( int i = 0; i < M; i++ ) {
		cin >> edges[i].a >> edges[i].b >> edges[i].cost; --edges[i].a, --edges[i].b;
	}
	
	Unionfind tree(N);
	sort(edges, edges + M);
	int cost = 0;
	for ( int i = 0; i < M && selected.size() < N - 1; i++ ) {
		if ( !tree.same(edges[i].a, edges[i].b) ) {
			tree.unite(edges[i].a, edges[i].b);
			selected.push_back(i);
			cost += edges[i].cost;
		}
	}
		
	int ans = 0, num = 0;
	for ( int idx : selected ) {
		Unionfind tree2(N);
		int cnt = 0, cost2 = 0;
		for ( int i = 0; i < M; i++ ) {
			if ( i != idx && !tree2.same(edges[i].a, edges[i].b) ) {
				tree2.unite(edges[i].a, edges[i].b);
				cost2 += edges[i].cost;
				cnt++;
			}
		}
		if ( cnt < N - 1 || cost2 > cost ) {
			ans += edges[idx].cost;
			num++;
		}
	}

	cout << num << " " << ans << endl;

	return ( 0 );
}