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;

const int N = 505;
const int inf = 1e9;

struct Edge {
  int u, v, cost;
  Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
  bool operator==(const Edge& e) const {
    return e.u == u && e.v == v && e.cost == cost;
  }
  bool operator<(const Edge& e) const {
    return cost < e.cost;
  }
};

int par[N];
int n, m;

int find(int u) {
  return par[u] = (par[u] == u? u : find(par[u]));
}

void merge(int u, int v) {
  u = find(u);
  v = find(v);
  par[u] = v;
}

int mst(vector<Edge>& edges, vector<Edge>& used, Edge non) {
  int cost = 0;
  for (int i = 0; i < N; i++) par[i] = i;
  int done = 0;
  for (auto it : edges) {
    if (it == non) continue;
    if (find(it.u) != find(it.v)) {
      merge(it.u, it.v);
      cost += it.cost;
      done++;
      used.push_back(it);
    }
    if (done + 1 == n) break;
  }
  if (done + 1 != n) return inf;
  return cost;
}

int main() {
  scanf("%d %d", &n, &m);
  vector<Edge> edges;
  for (int i = 0; i < m; i++) {
    int u, v, cost;
    scanf("%d %d %d", &u, &v, &cost);
    edges.push_back(Edge(u, v, cost));
  }
  sort(edges.begin(), edges.end());
  vector<Edge> used;
  int mst_cost = mst(edges, used, Edge(-1, -1, -1));
  int ans = 0, cost = 0;
  for (auto it : used) {
    vector<Edge> tmp;
    if (mst_cost < mst(edges, tmp, it)) {
      ans++;
      cost += it.cost;
    }
  }
  printf("%d %d\n", ans, cost);
  return 0;
}