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<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<list>
#include<queue>
#include<cmath>
#include<functional>
#include<algorithm>
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;



class UnionFind{
	vector<int> par;
	vector<int> rank;
public:
	UnionFind(int n):par(n),rank(n){
		init(n);
	}
	void init(int n){
		for(int i=0;i<n;i++){
			par[i]=i;
			rank[i]=0;
		}
	}
	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(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);
	}
};



struct Edge{
	int s,t;
	int cost;
	bool operator<(const Edge &e)const{return cost<e.cost;}
};



int mst(const vector<Edge> &edges,int v,vector<int> &used){
	int res=0;
	UnionFind uf(v);
	rep(i,edges.size()){
		const Edge &e=edges[i];
		if(!uf.same(e.s,e.t)){
			uf.unite(e.s,e.t);
			res+=e.cost;
			used.push_back(i);
		}
	}
	return res;
}


int mst(const vector<Edge> &edges,int v,int unuse){
	int res=0;
	UnionFind uf(v);
	rep(i,edges.size()){
		if(i==unuse)continue;
		const Edge &e=edges[i];
		if(!uf.same(e.s,e.t)){
			uf.unite(e.s,e.t);
			res+=e.cost;
		}
	}
	rep(i,v)if(!uf.same(0,i))return -1;
	return res;
}



int main(){
	int n,m;
	vector<Edge> edges;
	vector<int> maybealter;
	cin>>n>>m;
	rep(i,m){
		Edge e;
		cin>>e.s>>e.t>>e.cost;
		e.s--;e.t--;
		edges.push_back(e);
	}
	sort(edges.begin(),edges.end());
	int mincost=mst(edges,n,maybealter);
	int cnt=0;
	int sumcost=0;
	rep(i,n-1){
		int cost=mst(edges,n,maybealter[i]);
		if(cost==-1 || mincost!=cost){
			cnt++;
			sumcost+=edges[maybealter[i]].cost;
		}
	}
	cout<<cnt<<' '<<sumcost<<endl;
	return 0;
}