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 <map>
#include <algorithm>
#include <set>
using namespace std;
const int INF = 1 << 28;
int n,m;
vector< vector<int> > cost;
vector<int> mincost;

vector<bool> used;
vector<pair<int,int> > edge;
int prim(){
  mincost = vector<int>(n);
  used = vector<bool>(n);
  for(int i = 0;i < n;i++){
	mincost[i] = INF;
	used[i] = false;
  }
  vector<int> keep_edge = vector<int>(n,INF);
  mincost[0] = 0;
  int res = 0;
  while(true){
	int v = -1;
	for(int u = 0;u < n;u++){
	  if(!used[u] && (v == -1 || mincost[u] < mincost[v]))v = u;
	}
	if(v == -1)break;
	used[v] = true;
	res += mincost[v];
	edge.emplace_back(v,keep_edge[v]);
	for(int u = 0;u < n;u++){
	  if(cost[u][v] < mincost[u]){
		keep_edge[u] = v;
		mincost[u] = cost[u][v];
	  }
	}
  }
  return res;
}
int main(){
  cin >> n >> m;
  cost = vector<vector<int> >(n,vector<int>(n,INF));
  
  for(int i = 0;i < m;i++){
	int f,t,c;
	cin >> f >> t >> c;
	f--;t--;
	cost[f][t] = c;
	cost[t][f] = c;
  }
  int res = prim();
  int sum_cost = 0;
  vector<pair<int,int> > small_tree = vector<pair<int,int> >( edge);
  vector<pair<int,int> > ans_keep;
  for(int i = 1;i < small_tree.size();i++){
	pair<int,int> tmp = small_tree[i];
	int tmp_c = cost[tmp.first][tmp.second];
	
    cost[tmp.first][tmp.second] = INF;
    cost[tmp.second][tmp.first] = INF;
	if(res != prim()){
	  int a,b;
	  a = (tmp.first < tmp.second ? tmp.first : tmp.second);
	  b = (tmp.first < tmp.second ? tmp.second : tmp.first);
	  ans_keep.emplace_back(a,b);
	  sum_cost += tmp_c;
	}
	cost[tmp.first][tmp.second] = tmp_c;
	cost[tmp.second][tmp.first] = tmp_c;
	
	

  }
  cout << ans_keep.size() << " " << sum_cost << endl;
  // sort(ans_keep.begin(),ans_keep.end());
  // for(pair<int,int> p : ans_keep){
  // 	cout << p.first << " " << p.second << endl;
  // 	}
  


  
  
  return 0;
}