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>
using namespace std;
#define int long long
struct UnionFind{
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int size){init(size);}
  void init(int size){
    r.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) r[i]=1,p[i]=i;
  }
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};
struct edge{
  int from,to,cost,used;
  edge(){}
  edge(int from,int to,int cost):from(from),to(to),cost(cost){used=0;}
  bool operator<(const edge& e) const{
    return cost<e.cost;
  }
};
int kruskal(int N,vector<edge> &edges){
  int res=0;
  sort(edges.begin(),edges.end());
  UnionFind uf(N+1);
  for(int i=0;i<(int)edges.size();i++){
    edge& e=edges[i];
    if(!uf.same(e.from,e.to)){
      res+=e.cost;
      e.used=1;
      uf.unite(e.from,e.to);
    }
  }
  return res;
}
vector<int> G[555];
int C[555][555];
int INF=1LL<<55LL;
int num,ans;
int V,E;
unordered_set<int> dfs(int v,int p){
  //cout<<v<<" "<<p<<endl;
  unordered_set<int> res;
  res.insert(v);
  for(int u:G[v]){
    if(u==p) continue;
    int tmp=C[v][u];
    unordered_set<int> chd=dfs(u,v);
    int alt=INF;
    for(int i=0;i<V;i++){
      for(int j=i+1;j<V;j++){
	if(i==u&&j==v) continue;
	if(i==v&&j==u) continue;
	if(chd.count(i)^chd.count(j)) alt=min(alt,C[i][j]);
      }
    }
    //cout<<alt<<" "<<tmp<<endl;
    if(alt>tmp){
      num++;
      ans+=tmp;
    }
    for(int i:chd) res.insert(i);
  }
  return res;
}
signed main(){
  cin>>V>>E;
  vector<edge> edges(E);
  for(int i=0;i<E;i++){
    cin>>edges[i].from>>edges[i].to>>edges[i].cost;
    edges[i].from--;
    edges[i].to--;
  }
  kruskal(V,edges);
  for(int i=0;i<555;i++)
    for(int j=0;j<555;j++)
      C[i][j]=INF;
  for(int i=0;i<E;i++){
    //cout<<i<<" "<<edges[i].used<<endl;
    if(edges[i].used){
      G[edges[i].from].push_back(edges[i].to);
      G[edges[i].to].push_back(edges[i].from);
    }
    C[edges[i].from][edges[i].to]=edges[i].cost;
    C[edges[i].to][edges[i].from]=edges[i].cost;
  }
  num=ans=0;
  dfs(0,-1);
  cout<<num<<" "<<ans<<endl;
  return 0;
}