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 int long long
using namespace std;

struct UnionFind{
	vector<int> rnk,par;

	UnionFind(int sz) : rnk(sz,0),par(sz){
		for(int i = 0;i < sz;i++) par[i] = i;
	}

	int find(int x){
		if(par[x] == x) return x;
		return par[x] = find(par[x]);
	}

	void unite(int x,int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(rnk[x] < rnk[y]) swap(x,y);
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
	
	bool same(int x,int y){
		return (find(x) == find(y));
	}
};

template<class T>
struct Edge{
	int from,to,id;
	T cost;
	Edge(int to,T cost,int id) : to(to),cost(cost),id(id){}
	Edge(int from,int to,T cost,int id) : from(from),to(to),cost(cost),id(id){}
};

template<class T>
using WeightedGraph = vector<vector<Edge<T>>>;
using Graph = vector<vector<int>>;
template<class T>
using Matrix = vector<vector<T>>;

template <class T>
T kruskal(int n,vector<Edge<T>> &edges){
	T ret = 0;
	sort(edges.begin(),edges.end(),[](const Edge<T> &e1,const Edge<T> &e2){
		return e1.cost < e2.cost;
	});
	UnionFind uf(n);
	for(const Edge<T> &e : edges){
		if(!uf.same(e.from,e.to)){
			ret += e.cost;
			uf.unite(e.from,e.to);
		}
	}
	return ret;
}

signed main(){
	int n,m;
	cin >> n >> m;
	vector<Edge<int>> edges;
	for(int i = 0;i < m;i++){
		int s,d,c;
		cin >> s >> d >> c; s--;d--;
		edges.emplace_back(s,d,c,i);
	}
	sort(edges.begin(),edges.end(),[](const Edge<int> &e1,const Edge<int> &e2){
		return e1.cost < e2.cost;
	});
	int mstCost = 0;
	UnionFind uf(n);
	vector<Edge<int>> candEdge;
	for(const auto &e : edges){
		if(!uf.same(e.from,e.to)){
			mstCost += e.cost;
			uf.unite(e.from,e.to);
			candEdge.push_back(e);
		}
	}
	int num = 0,sum = 0;
	for(const auto &c : candEdge){
		UnionFind uf2(n);
		int cost = 0;
		bool isAllConnected = true;
		for(const auto &e : edges){
			if(e.id != c.id && !uf2.same(e.from,e.to)){
				cost += e.cost;
				uf2.unite(e.from,e.to);
			}
		}
		for(int i = 0;i < n - 1;i++){
			if(!uf2.same(i,i + 1)) isAllConnected = false;
		}
		if(!isAllConnected || cost != mstCost){
			num++;
			sum += c.cost;
		}
	}
	cout << num << " " << sum << endl;
}