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;

struct LowLink {
  int n, pos;
  vector<int> ord, low, par, blg;  
  vector<vector<int> > G, C, T;

  vector<int> ap;
  vector<pair<int, int> > bs;

  LowLink(int n) : n(n), pos(0), ord(n, -1), low(n), par(n, -1), blg(n, -1), G(n) {}  

  void add_edge(int u, int v) {
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  bool is_bridge(int u, int v) {
    if ( ord[u] > ord[v] ) swap(u, v);
    return ord[u] < low[v];    
  }

  void dfs(int v) {
    ord[v] = low[v] = pos++;
    for ( int u : G[v] ) {
      if ( u == par[v] ) continue;
      if ( ~ord[u] ) {
	low[v] = min(low[v], ord[u]);
	continue;
      }
      par[u] = v;
      dfs(u);
      low[v] = min(low[v], low[u]);
      if ( is_bridge(u, v) ) bs.emplace_back(u, v);      
    }
  }

  void fill_component(int v) {
    C[blg[v]].emplace_back(v);
    for ( int u : G[v] ) {
      if ( ~blg[u] ) continue;
      blg[u] = blg[v];
      fill_component(u);      
    }
  }

  void add_component(int v, int &k) {
    if ( ~blg[v] ) return;
    blg[v] = k++;
    C.emplace_back();
    fill_component(v);    
  }

  void build() {
    for ( int i = 0; i < n; i++ ) {
      if ( ord[i] < 0 ) dfs(i);
    } 
  }  
};

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

struct UnionFind {
  int n;
  vector<int> r, p;
  UnionFind() {}
  UnionFind(int sz) : n(sz), r(sz, 1), p(sz, 0) {
    iota(p.begin(), p.end(), 0);    
  }
  int find(int x) {
    return (x==p[x] ? x : p[x]=find(p[x]));    
  }
  bool same(int x, int y) {
    return find(x) == find(y);    
  }
  void unite(int x, int y) {
    x = find(x); y = find(y);
    if ( x == y ) return;
    if ( r[x] < r[y] ) swap(x, y);
    r[x] += r[y];
    p[y] = x;    
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<Edge> es(M);  
  for ( int i = 0; i < M; i++ ) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    es[i] = Edge{u, v, c};    
  }

  sort(es.begin(), es.end());  

  vector<int> use;
  int cost = 0;
  {
    UnionFind uf(N);
    int cnt = 0;
    for ( int i = 0; i < M; i++ ) {
      int u = es[i].u, v = es[i].v, c = es[i].c;
      if ( uf.same(u, v) ) continue;
      cost += c;
      uf.unite(u, v);
      use.emplace_back(i);
      cnt++;
      if ( cnt == N-1 ) continue;    
    }
  }

  int ans = 0, anscost = 0;  
  for ( int i = 0; i < N-1; i++ ) {
    UnionFind uf(N);
    int ncost = 0;
    int ncnt = 0;    
    for ( int j = 0; j < M; j++ ) {
      if ( use[i] == j ) continue;
      int u = es[j].u, v = es[j].v, c = es[j].c;
      if ( uf.same(u, v) ) continue;
      ncost += c;
      uf.unite(u, v);
      ncnt++;
      if ( ncnt == N-1 ) continue;      
    }

    if ( ncost > cost || ncnt < N-1 ) {
      ans++;
      anscost += es[use[i]].c;      
    }
  }

  cout << ans << " " << anscost << endl;
  
  return 0;
}