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>

#define phb push_back
#define mkp make_pair
#define frs first
#define scn second
#define sz(x) int((x).size())
using namespace std;

const int kInf = 1000000000;
typedef pair< int, int > Pr;
typedef pair< int, Pr > Prr;

int N, M;
Prr E[50010];
vector< int > NE;

int nset[510];

void read();
void solve();
int kruskal(int);

int find_set(int x) {
  if (~nset[x])
    return nset[x] = find_set(nset[x]);
  return x;
}

void union_set(int x, int y) {
  nset[find_set(y)] = find_set(x);
}

bool cmpf(const Prr &, const Prr &);

int main() {
  read();
  solve();
  return 0;
}

void read() {
  int u, v, c;

  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    cin >> u >> v >> c;
    E[i] = mkp(c, mkp(u, v));
  }
}

void solve() {
  int res, mcst, csum;

  stable_sort(&E[0], &E[M], cmpf);
  mcst = kruskal(-1);

  res = csum = 0;
  for (int i = 0; i < N - 1; ++i)
    if (kruskal(NE[i]) > mcst)
      ++res, csum += E[NE[i]].frs;

  cout << res << " " << csum << "\n";
}

int kruskal(int fid) {
  fill(&nset[0], &nset[510], -1);

  int i, j, ret = 0;

  if (fid == -1) {
    for (i = j = 0; i < M && j < N - 1; ++i) {
      int u = E[i].scn.frs, v = E[i].scn.scn;

      if (find_set(u) != find_set(v))
        ret += E[i].frs, union_set(u, v), ++j, NE.phb(i);
    }
  }
  else {
    for (i = j = 0; i < M && j < N - 1; ++i) {
      if (i == fid) continue;

      int u = E[i].scn.frs, v = E[i].scn.scn;

      if (find_set(u) != find_set(v))
        ret += E[i].frs, union_set(u, v), ++j;
    }
  }

  return j == N - 1 ? ret : kInf;
}

bool cmpf(const Prr &ra, const Prr &rb) {
  return ra.frs < rb.frs;
}