Problem: Example

Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3


Output

1 3

Solution (in CPP):

Solution:
// AOJ 1350
#include<iostream>
#include<algorithm>
#include<map>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int integer;

struct edge { integer u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
  return e1.cost < e2.cost;
}

const integer EMAX = 1e6;
const integer VMAX = 1000;
const integer INF = 1e10;
edge es[EMAX];
bool used[EMAX];
integer V, E;

integer par[VMAX];
integer lank[VMAX];

void init_union_find(integer N) {
  for (integer i = 0; i < N; i++) {
    par[i] = i;
    lank[i] = 0;
  }
}

integer find(integer x) {
  if (x == par[x]) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

void unite(integer x, integer y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  if (lank[x] < lank[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (lank[x] == lank[y]) lank[x]++;
  }
}

bool same(integer x, integer y) {
  return find(x) == find(y);
}

integer kraskal(bool causes_side_effect) {
  init_union_find(V);
  integer res = 0;
  REP(i, E) {
    edge e = es[i];
    if (e.cost == INF) continue;
    if (!same(e.u, e.v)) {
      unite(e.u, e.v);
      res += e.cost;
      if (causes_side_effect) {
        used[i] = true;
      }
    }
  }
  return res;
}

bool connected() {
  REP(i, V) {
    if (not same(0,i)) return false;
  }
  return true;
}

pair<integer,integer> solve() {
  sort(es, es + E, comp);
  REP(i, E) { used[i] = false; }
  integer mincost = kraskal(true);

  integer edges = 0, total_cost = 0;
  REP(i, E) {
    if (not used[i]) continue;
    integer temp = es[i].cost;
    es[i].cost = INF;
    integer cost = kraskal(false);
    if (mincost < cost or !connected()) {
      edges++;
      total_cost += temp;
    }
    es[i].cost = temp;
  }
  return make_pair(edges, total_cost);
}

int main() {
  cin >> V >> E;
  REP(i, E) {
    cin >> es[i].u >> es[i].v >> es[i].cost;
    es[i].u--; es[i].v--;
  }
  pair<integer,integer> p = solve();
  cout << p.first << " " << p.second << endl;
}