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<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;

#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)


class E{
	public:
	int come,to,val;
	bool check;
	E(int come,int to,int val):come(come),to(to),val(val){
		check = false;
	}
};

class Q{
	public:
	int now,val;
	E edge;
	Q(int now,int val,E edge):now(now),val(val),edge(edge.come,edge.to,edge.val){}
	bool operator<(const Q& a)const{
		return val>a.val;
	}
};


const int N = 555;
const int INF = 1000000000;
int n,m;
vector<E> edge[N];
int visit[N];

vector<E> g[N];


bool contain(E ein){
	rep(i,g[ein.come].size()){
		E e = g[ein.come][i];
		if(e.to == ein.to)return true;
	}
	return false;
}

bool saiki(int now,int goal,int cost){
	
	//printf("now %d   goal %d   cost %d\n",now,goal,cost);
	
	if(now==goal){
		return true;
	}
	
	visit[now] = 1;
	
	bool ret = false;
	rep(i,g[now].size()){
		E e = g[now][i];
		if(visit[e.to]==1)continue;
		
		bool res = saiki(e.to, goal,cost);
		if(res==true){
			if(e.val==cost)g[now][i].check=true;
			ret = true;
		}
	}
	
	return ret;
}

void delcheck(E ein){
	//printf("delc  %d %d %d\n",ein.come,ein.to,ein.val);
	
	rep(i,N)visit[i]=0;
	saiki(ein.come, ein.to, ein.val);
	
}

int main(){
	cin>>n>>m;
	
	int mcost = INF;
	
	rep(i,m){
		int a,b,c;
		cin>>a>>b>>c;
		edge[a].push_back(E(a,b,c));
		edge[b].push_back(E(b,a,c));
	}
	
	
	priority_queue<Q> que;
	que.push(Q(1,0,E(-1,-1,-1)));
	
	rep(i,N)visit[i]=0;
	
	vector<E> use;
	
	while(1){
		if(que.empty())break;
		Q u = que.top();
		que.pop();
		
		if(visit[u.now]==1)continue;
		visit[u.now]=1;
		
		use.push_back(u.edge);
		
		rep(i,edge[u.now].size()){
			E e = edge[u.now][i];
			que.push(Q(e.to, e.val, e));
		}
	}
	
	/*
	rep(i,use.size()){
		E e = use[i];
		printf("come%d to%d val%d\n",e.come,e.to,e.val);
		
	}*/
	
	rep(i,use.size()){
		if(use[i].to==-1)continue;
		E e = use[i];
		g[e.come].push_back(E(e.come,e.to,e.val));
		g[e.to].push_back(E(e.to,e.come,e.val));	
	}
	
	
	
	rep(i,N){
		rep(j,edge[i].size()){
			E e = edge[i][j];
			if(!contain(e)){
				delcheck(e);
			}
		}
	}
	
	int cont = 0;
	int sum = 0;
	rep(i,N){
		rep(j,g[i].size()){
			E e = g[i][j];
			//printf("!!! %d %d %d %d\n",e.come,e.to,e.val,e.check);
			if(e.check==false){
				cont++;
				sum+=e.val;
			}
		}
	}
	
	printf("%d %d\n",cont/2,sum/2);
}

/*
4 4
1 2 3
1 3 3
2 3 3
2 4 3

*/