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 <algorithm>
#include <vector>
using namespace std;
#define DEBUG(x) cerr << #x << " = " << x << endl
struct UnionFind {
  vector<int> data;
  UnionFind(int n) : data(n, -1) { }
  int root(int x) {
    return data[x] < 0 ? x : (data[x] = root(data[x]));
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  void merge(int x, int y) {
    x = root(x); y = root(y);
    if(x != y) {
      if(size(y) > size(x)) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
  }
  int size(int x) {
    return -data[root(x)];
  }
  int count_union() {
    int res = 0;
    for(int v : data) if(v < 0) ++res;
    return res;
  }
};
struct Edge {
  int from, to, cost;
  Edge(int from_, int to_, int cost_) : from(from_), to(to_), cost(cost_) { }
  bool operator <(const Edge &rhs) const {
    return cost < rhs.cost;
  }
};
int main() {
  int N, M; cin >> N >> M;
  vector<Edge> G;
  for(int i = 0; i < M; ++i) {
    int from, to, cost;
    cin >> from >> to >> cost;
    --from; --to;
    G.emplace_back(from, to, cost);
  }
  sort(G.begin(), G.end());
  vector<int> need;
  long long mincost = 0;
  {
    UnionFind uf(N);
    for(int i = 0; i < M; ++i) {
      if(uf.same(G[i].from, G[i].to) == false) {
        mincost += G[i].cost;
        uf.merge(G[i].from, G[i].to);
        need.push_back(i);
      }
    }
  }
  int ansnum = 0;
  long long anscost = 0;
  for(int e : need) {
    long long cost = 0;
    UnionFind uf(N);
    for(int i = 0; i < M; ++i) {
      if(i == e) continue;
      if(uf.same(G[i].from, G[i].to) == false) {
        cost += G[i].cost;
        uf.merge(G[i].from, G[i].to);
      }
    }
    if(cost == mincost && uf.count_union() == 1) {
    }
    else {
      ++ansnum;
      anscost += G[e].cost;
    }
  }
  cout << ansnum << " " << anscost << endl;
}