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 <algorithm>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

struct Edge{
  int cost, from, to;
  Edge(int cost, int from, int to):
    cost(cost), from(from), to(to) {}
};

bool operator<(const Edge& a, const Edge& b){
  return a.cost != b.cost ? a.cost < b.cost : a.from != b.from ? a.from < b.from : a.to < b.to;
}

struct UnionFind{
  vector<int> data;
  UnionFind(int n) : data(n, -1) {}
  bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x != y){
      if(data[y] < data[x]) swap(x,y);
      data[x] += data[y];//高さを更新
      data[y] = x;//親を更新
    }
    return x != y;
  }
  bool same(int x, int y){ return find(x) == find(y); }
  int find(int x){
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
};

int kruskal(vector<Edge> &E, int N){
  UnionFind uf(N);
  int ret = 0, t = 0;
  for(int i = 0; i < E.size(); ++i){
    int c = E[i].cost, s = E[i].from, d = E[i].to;
    if(!uf.same(s,d)){
      ret += c;
      uf.unite(s,d);
      ++t;
      if(t == N-1) break;
    }
  }
  return ret;
}

pair<int, vector<int> > mst(vector<Edge> &E, int N){
  UnionFind uf(N);
  int ret = 0, t = 0;
  vector<int> V;
  for(int i = 0; i < E.size(); ++i){
    int c = E[i].cost, s = E[i].from, d = E[i].to;
    if(!uf.same(s,d)){
      ret += c;
      uf.unite(s,d);
      ++t;
      V.push_back(i);
      if(t == N-1) break;
    }
  }
  return make_pair(ret,V);
}

pair<int,int> solve(vector<Edge> &E, int N){
  pair<int,vector<int> > p = mst(E,N);
  int min_cost = p.first;
  vector<int> V = p.second;
  int ans = 0, INF = 1e9, c = 0;
  for(int i = 0; i < N-1; ++i){
    vector<Edge> E_ = E;
    E_[V[i]].cost = INF;
    sort(E_.begin(), E_.end());
    if(kruskal(E_,N) != min_cost){
      ++ans;
      c += E[V[i]].cost;
    }
  }
  return make_pair(ans,c);
}

int main(){
  int N, M;
  cin >> N >> M;
  vector<Edge> E;
  int s, d, c;
  for(int i = 0; i < M; ++i){
    cin >> s >> d >> c;
    --s;--d;
    E.push_back(Edge(c,s,d));
  }
  sort(E.begin(), E.end());
  pair<int,int> ans = solve(E,N);
  cout << ans.first << " " << ans.second << endl;
  return 0;
}