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

#define INF 1e9

// UnionFind??¨ ??????????????????
class UnionFindTree{
public:
  UnionFindTree();
  UnionFindTree(int size);
  void init(int size);
  void unite(int a, int b);
  bool same(int a, int b);
  bool isConnected(void);
private:
  int m_size, unite_count;
  vector<int> parent;
  vector<int> rank;
  int find(int a);
};

// ?????????????????????
UnionFindTree::UnionFindTree(){};
UnionFindTree::UnionFindTree(int size){ init(size); };

// UF??¨????????????
void UnionFindTree::init(int size){
  m_size = size;
  unite_count = 0;
  parent.clear();
  rank.clear();
  for(int i = 0; i < size; i++){
    parent.push_back(i);
    rank.push_back(0);
  }
  return;
}

// UF??¨??§???????????£?????????
void UnionFindTree::unite(int a, int b){
  int x = find(a);
  int y = find(b);
  // ?????§???????????£???????????????????????????
  if(x == y){ return; }

  unite_count++;
  if(rank[x] < rank[y]){ parent[x] = y; }
  else{
    parent[y] = x;
    if(rank[x] == rank[y]){ rank[x]++; }
  }
  return;
}

// UF??¨??§???????????????????????????????????????
bool UnionFindTree::same(int a, int b){
  return find(a) == find(b);
}

// UF??¨??§?????????????????????????????¨???????????????????????????
bool UnionFindTree::isConnected(void){
  return unite_count == m_size - 1;
}

// UF??¨?????????????????????
int UnionFindTree::find(int a){
  if(parent[a] != a){ parent[a] = find(parent[a]); }
  return parent[a];
}

// ?????????????????? ?????????
// v: ????????°, adjlist: ??£??\?????????(first: ???????????????, second: ?????????)
vector<pair<int, pair<int, int> > > kruskal_pre(int v, vector<vector<pair<int, int> > > adjlist){
  vector<pair<int, pair<int, int> > > edge; // first: ???????????????, second: ???????????????
  for(int i = 0; i < v; i++)
    for(int j = 0; j < adjlist[i].size(); j++)
      edge.push_back(make_pair(adjlist[i][j].first, make_pair(i, adjlist[i][j].second)));
  sort(edge.begin(), edge.end());

  return edge; // ?????????: ???????????????????????????
}

// ?????????????????? ??¬??????
// v: ????????°, edge: ???????????????????????????(first: ???????????????, second: ???????????????)
pair<int, vector<bool> > kruskal(int v, vector<pair<int, pair<int, int> > > edge, vector<bool> canUse){
  int length = 0; // ??¨????????????
  UnionFindTree uf(v); // UF??¨?????£?¨???¨?????????
  vector<bool> useEdge(edge.size(), false);

  // ???????????????????????????????????????????????????????????£?????????????????§?????????
  for(int i = 0; i < edge.size() && !uf.isConnected(); i++){
    if(!canUse[i]){ continue; }
    
    // i??????????°???????????????????
    int cost = edge[i].first;
    int a = edge[i].second.first;
    int b = edge[i].second.second;
    // ????????????????????????????????£????????????????£???°???
    if(uf.same(a, b)){ continue; }

    // UF??¨?????£??????????????????????????´??°
    uf.unite(a, b);
    length += cost;
    useEdge[i] = true;
  }

  if(!uf.isConnected()){ length = INF; }
  return make_pair(length, useEdge); // ?????????: ??¨????????????
}


int main(void){
  int n, m;
  cin >> n >> m;

  int s, g, c;
  vector<pair<int, pair<int, int> > > edge;
  for(int i = 0; i < m; i++){
    cin >> s >> g >> c;
    edge.push_back(make_pair(c, make_pair(s - 1, g - 1)));
  }
  sort(edge.begin(), edge.end());

  vector<bool> canUse(m, true);
  pair<int, vector<bool> > tmp = kruskal(n, edge, canUse);
  int ans_cost = tmp.first;
  vector<bool> ans_edge = tmp.second;

  int result = 0, sum = 0;
  for(int i = 0; i < ans_edge.size(); i++){
    if(ans_edge[i]){
      canUse[i] = false;
      int test = kruskal(n, edge, canUse).first;
      canUse[i] = true;
      if(test > ans_cost){
        ++result;
        sum += edge[i].first;
      }
    }
  }

  // ??????
  cout << result << " " << sum << endl;

  return 0;
}