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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

/* UnionFind */

struct UnionFind{
  vector<int> data, tree_size;
  UnionFind(int s):data(s,-1),tree_size(s,1) {}
  
  int root(int x){
    if(data[x]==-1) return x;
    return data[x]=root(data[x]);
  }
  
  bool set(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y) return false;
    data[y]=x;
    tree_size[x] += tree_size[y];
    tree_size[y] = 0;
    return true;
  }
  
  bool check(int x,int y){
    x=root(x);
    y=root(y);
    return x==y;
  }
  
  int size(int x){
    return tree_size[root(x)];
  }
  
};


int n,m;
vector<pair<int,pair<int,int> > > vec;

int main(){

  scanf("%d%d",&n,&m);
  
  for(int i=0;i<m;i++){
    int s,d,c;

    scanf("%d%d%d",&s,&d,&c);
    s--; d--;
    vec.push_back({c,{s,d}});
  }

  sort(vec.begin(),vec.end());

  UnionFind uf(n);

  int l = 0, r = 0;
  int sqrtM = (int)sqrt(m);

  int ans1 =0, ans2=0;
  
  for(int i=1;i<=10000;i++){

    while(r < m && vec[r].first == i) r++;

    for(int j=l;j<r;j+=sqrtM){
      UnionFind uf2 = uf;

      for(int k=j+sqrtM;k<r;k++){
        uf2.set(vec[k].second.first, vec[k].second.second);
      }

      for(int k=j;k<min(r,j+sqrtM);k++){
        UnionFind uf3 = uf2;

        for(int w=j;w<min(r,j+sqrtM);w++){
          if(k == w) continue;
          uf3.set(vec[w].second.first, vec[w].second.second);
        }

        if(!uf3.check(vec[k].second.first, vec[k].second.second)){
          ans1++;
          ans2+=vec[k].first;
        }
        
      }

      for(int k=j;k<min(r,j+sqrtM);k++){
        uf.set(vec[k].second.first, vec[k].second.second);
      }
    }
    
    l = r;
  }

  printf("%d %d\n",ans1, ans2);
  
  return 0;
}