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<vector>
#include<algorithm>
#include<numeric>
#include<set>
#include<tuple>

using namespace std;

vector<tuple<int,int,int> > edges;

struct UnionFind{
  vector<int> par;
  UnionFind(int n):par(n){
    iota(begin(par),end(par),0);
  }
  int find(int x){
    return (x==par[x])?x:par[x]=find(par[x]);
  }
  void unite(int a,int b){
    par[find(a)]=find(b);
  }
};

int kr(UnionFind uf,int x){
  int c=0;
  for(int i=x;i<edges.size();i++){
    int s=get<1>(edges[i]),d=get<2>(edges[i]);
    if(uf.find(s)!=uf.find(d)){
      c+=get<0>(edges[i]);
      uf.unite(s,d);
    }
  }
  set<int> s;
  for(int i=0;i<uf.par.size();i++){
    s.insert(uf.find(i));
  }
  return (s.size()==1)?c:1e9;
}

int main(){
  int N,M;
  cin>>N>>M;
  for(int i=0;i<M;i++){
    int S,D,C;
    cin>>S>>D>>C;
    edges.emplace_back(C,S-1,D-1);
  }
  sort(begin(edges),end(edges));
  UnionFind uf(N);
  int tc=kr(uf,0);
  int cc=0;
  int ans=0;
  int nac=0;
  for(int i=0;i<edges.size();i++){
    int s=get<1>(edges[i]),d=get<2>(edges[i]);
    if(uf.find(s)!=uf.find(d)){
      if(tc!=cc+kr(uf,i+1)){
	ans++;
	nac+=get<0>(edges[i]);
      }
      uf.unite(s,d);
      cc+=get<0>(edges[i]);
    }
  }
  cout<<ans<<' '<<nac<<endl;
}