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 <stdio.h>
#include <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()
#define X first
#define Y second

const int INF = 1e9;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={0, 1, 0, -1}, dy[4]={-1, 0, 1, 0};
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

/* struct P {
	int x, y, n;
	P(int n, int x, int y):n(n), x(x), y(y){}
	P(){}
}; */

/** Union-Find **/
const int MAX_N = 1000;
const int MAX_E = 50000;

class UnionFind {
public:
	int par[MAX_N];
	int rank[MAX_N];
	
	void init(int n)
	{
		rep(i, n) {
			par[i]=i;
			rank[i]=0;
		}
	}
	
	int find(int x)
	{
		if (par[x] == x) {
			return x;
		} else {
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);
		if (x == y) return;
		
		if (rank[x] < rank[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
	}
	
	bool same(int x, int y)
	{
		return find(x) == find(y);
	}
};

/** 最小全域木 kruskal法 O(|E|log|V|) **/
struct edge {int u, v, cost;};

bool comp(const edge& e1, const edge& e2)
{
	return e1.cost < e2.cost;
}

edge es[MAX_E];
vector<int> tmp;
int V, E;

int kruskal(int notuse)
{
	UnionFind UF;
	UF.init(V);
	int res=0;
	for (int i=0; i<E; i++) {
		if (i == notuse) continue;
		
		edge e = es[i];
		if (!UF.same(e.u, e.v)) {
			UF.unite (e.u, e.v);
			
			if (notuse==-1)
				tmp.push_back(i);
			
			res += e.cost;
		}
	}
	return res;
}

int main()
{
	
	cin>>V>>E;
	rep(i, E) {
		cin>>es[i].u>>es[i].v>>es[i].cost;
		es[i].u--, es[i].v--;
	}
	
	sort(es, es+E, comp);
	int mst_cost = kruskal(-1);
	
	int ans=0, sum=0;
	rep(i, tmp.size()) {
		if (mst_cost != kruskal(tmp[i])) {ans++, sum+=es[tmp[i]].cost;}
	}
	
	cout << ans << " " << sum << endl;
}