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;
struct unionfind{
  vector<int> p;
  unionfind(int n){
    p = vector<int>(n, -1);
  }
  int root(int x){
    if (p[x] == -1){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    p[x] = y;
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<tuple<int, int, int>> E(M);
  for (int i = 0; i < M; i++){
    int S, D, C;
    cin >> S >> D >> C;
    S--;
    D--;
    E[i] = make_tuple(C, S, D);
  }
  sort(E.begin(), E.end());
  unionfind UF(N);
  vector<bool> used(M, false);
  int sum = 0;
  for (int i = 0; i < M; i++){
    int C = get<0>(E[i]);
    int S = get<1>(E[i]);
    int D = get<2>(E[i]);
    if (!UF.same(S, D)){
      used[i] = true;
      UF.unite(S, D);
      sum += C;
    }
  }
  int ans1 = 0;
  int ans2 = 0;
  for (int i = 0; i < M; i++){
    if (used[i]){
      int sum2 = 0;
      unionfind UF2(N);
      int cnt = 0;
      for (int j = 0; j < M; j++){
        if (i != j){
          int C = get<0>(E[j]);
          int S = get<1>(E[j]);
          int D = get<2>(E[j]);
          if (!UF2.same(S, D)){
            UF2.unite(S, D);
            cnt++;
            sum2 += C;
          }
        }
      }
      if (sum2 > sum || cnt < N - 1){
        ans1++;
        ans2 += get<0>(E[i]);
      }
    }
  }
  cout << ans1 << ' ' << ans2 << endl;
}