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>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

class UnionFind {
private:
  vector<ll> data;

public:
  UnionFind(ll n): data(n, -1) {}

  ll size(ll i) { return -data[find(i)]; }
  bool root(ll i) { return data[i] < 0; }
  bool same(ll i, ll j) { return find(i) == find(j); }

  ll find(ll i) { return root(i) ? i : (data[i] = find(data[i])); }

  bool unite(ll i, ll j) {
    if(same(i, j)) return false;
    data[find(i)] += data[find(j)];
    data[find(j)] = find(i);
    return true;
  }
};

struct edge {
  ll u, v, d, idx;
  bool active, used;
  bool operator<(const edge &e) const { return d < e.d; }
};

ll mst(ll n, vector<edge> &edges) {
  UnionFind uf(n);
  ll ret = 0;
  sort(edges.begin(), edges.end());
  for(edge &e : edges) if(e.active && uf.unite(e.u, e.v)) {
    ret += e.d;
    e.used = true;
  }
  set<ll> st;
  REP(i, 0, n) st.insert(uf.find(i));
  return st.size() == 1 ? ret : (1LL << 60);
}

int main(void) {
  ll N, M;
  cin >> N >> M;
  vector<edge> edges(M);
  REP(i, 0, M) {
    cin >> edges[i].u >> edges[i].v >> edges[i].d;
    edges[i].u--;
    edges[i].v--;
    edges[i].idx = i;
    edges[i].active = true;
    edges[i].used = false;
  }

  ll cost = mst(N, edges);
  vector<ll> candidate;
  for(edge &e : edges) if(e.used) candidate.push_back(e.idx);

  vector<bool> need(M, true);
  for(edge &e : edges) if(!e.used) need[e.idx] = false;

  for(ll k : candidate) {
    for(edge &e : edges) e.active = e.idx != k;
    ll c = mst(N, edges);
    if(c == cost) need[k] = false;
  }

  ll ans = 0, ansc = 0;
  for(edge &e : edges) if(need[e.idx]) {
    ans++;
    ansc += e.d;
  }
  cout << ans << " " << ansc << endl;
}