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>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

// graph template
template<typename T>
class Edge{
	public:
		int src, to; T cost;

		Edge(int to, T cost): src(-1), to(to), cost(cost){}
		Edge(int src, int to, T cost): src(src), to(to), cost(cost){}

		bool operator==(const Edge &e){
			return src==e.src and to==e.to and cost==e.cost;
		}
};
template<typename T>
using Edges = vector<Edge<T>>;
template<typename T>
using AdjacencyList = vector<Edges<T>>;
template<typename T>
using Matrix = vector<vector<T>>;

// kruskal.cpp depend on this.
// kruskal.cpp depend on this.
#ifndef UNION_FIND_TREE
#define UNION_FIND_TREE
template<typename T>
class UnionFindTree{
	private:
		int N;
		vector<int> parent, rank, size;
		vector<T> diff_weight;

		int find(int x){
			if(parent[x] == x){
				return x;
			}else{
				int r = find(parent[x]);
				diff_weight[x] += diff_weight[parent[x]];
				return parent[x] = r;
			}
		}

		T weight(int x){
			find(x);
			return diff_weight[x];
		}

	public:
		void init(int N = -1){
			if(N > this -> N){
				this -> N = N;
				parent.resize(N); rank.resize(N); size.resize(N); diff_weight.resize(N);
			}

			for(int i = 0; i < this -> N; i++){
				parent[i] = i; rank[i] = 0; size[i] = 1; diff_weight[i] = 0;
			}
		}

		UnionFindTree(int N = 0): N(N), parent(N), rank(N), size(N), diff_weight(N){
			init();
		}

		T diff(int x, int y){
			return weight(y) - weight(x);
		}

		// weight(y) = weight(x) + w となるようにmergeする
		bool unite(int x, int y, T w = 0){
			w += weight(x); w -= weight(y);
			x = find(x); y = find(y);
			if(x == y) return weight(y) - weight(x) == w;

			if(rank[x] < rank[y]){
				swap(x, y);
				w = -w;
			}

			parent[y] = x;
			size[x] += size[y];
			if(rank[x] == rank[y]) rank[x]++;
			diff_weight[y] = w;
			return true;
		}

		bool isSame(int x, int y){
			return find(x) == find(y);
		}
		
		int count(int x){
			return size[find(x)];
		}
};
#endif

template<typename T>
Edges<T> kruskal0(Edges<T> &edges, int V){
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b){return a.cost < b.cost;});
    UnionFindTree<T> tree(V);
	Edges<T> es;
    
    T ret = 0;
    for(auto &e: edges){
        if(not tree.isSame(e.src, e.to)){
            ret += e.cost;
            tree.unite(e.src, e.to);
			es.push_back(e);
        }
    }

    return es;
}

template<typename T>
T kruskal(Edges<T> &edges, int V){
    sort(edges.begin(), edges.end(), [](const Edge<T> &a, const Edge<T> &b){return a.cost < b.cost;});
    UnionFindTree<T> tree(V);
	int num = 0;
    
    T ret = 0;
    for(auto &e: edges){
        if(not tree.isSame(e.src, e.to)){
            ret += e.cost;
            tree.unite(e.src, e.to);
			num++;
        }
    }

    return (num == V-1 ? ret : INF);
}

int main(void){
	int N, M;
	cin >> N >> M;
	Edges<int> es;
	for(int i = 0; i < M; i++){
		int s, d, c;
		cin >> s >> d >> c;
		es.push_back(Edge<int>(--s, --d, c));
	}

	Edges<int> spanning_tree =  kruskal0(es, N);
	int cost = kruskal(es, N);

	int num = 0, sum = 0;
	for(auto e: spanning_tree){
		// printf("sp_tree: %d %d %d\n", e.src, e.to, e.cost);
		es.erase(find(es.begin(), es.end(), e));
		if(kruskal(es, N) > cost){
			num++;
			sum += e.cost;
		}
		es.push_back(e);
	}
	// debug(cost);

	cout << num << ' ' << sum << '\n';

	return 0;
}