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<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn = 50050*2;
const int maxm = 50050*2;
struct Edge
{
	int from,to,dist,id;
};
vector<int> G[maxn];
vector<Edge> edges;
Edge tt[maxm];
bool cmp(Edge a,Edge b)
{
	return a.dist<b.dist;
}
void add_edge(int a,int b,int c)
{
	edges.push_back((Edge){a,b,c});
	edges.push_back((Edge){b,a,c});
	int m=edges.size();
	G[a].push_back(m-2);
	G[b].push_back(m-1);
}
int n,m;
bool flag[maxn];
int f[maxn];
int find(int x)
{
	return x==f[x]?x:find(f[x]);
}
void add(int a,int b)
{
	int ta=find(a);
	int tb=find(b);
	f[ta]=tb;
}
bool vis[maxn],is[maxm];
void dfs1(int u)
{
	vis[u]=1;
	for(int i=0;i<G[u].size();i++)
	{
		int t=G[u][i];
		Edge e=edges[t];
		if(!vis[e.to]&&flag[t])
			dfs1(e.to);
	}
}
bool vis1[maxn];
bool dfs2(int u,int key)
{
	vis1[u]=1;bool ret= false;
	for(int i=0;i<G[u].size();i++)
	{
		int t=G[u][i];
		Edge e=edges[t];
		if(!vis[e.to]&&!flag[t]&&key==e.dist)
			return true;
		if(!vis1[e.to]&&vis[e.to])
			ret|=dfs2(e.to,key);
	}
	return ret;
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)
			f[i]=i;
		edges.clear();
		for(int i=1;i<=n;i++)
			G[i].clear();
		memset(flag,0,sizeof(flag));
		int a,b,c,ID=0;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add_edge(b,a,c);
			tt[ID]=(Edge){a,b,c,ID++};
			tt[ID]=(Edge){b,a,c,ID++};
		}
		sort(tt,tt+ID,cmp);
		for(int i=0;i<ID;i++)
		{
			int u=find(tt[i].from),v=find(tt[i].to);
			if(u!=v)
			{
				add(u,v);
				flag[tt[i].id]=flag[tt[i].id^1]=1;
			}
		}
		memset(is,0,sizeof(is));
		for(int i=0;i<edges.size();i++)
			if(flag[i]&&!is[i]&&!is[i^1])
		    {
		    	memset(vis,0,sizeof(vis));
		    	flag[i]=flag[i^1]=0;
		    	dfs1(edges[i].from);
		    	flag[i]=flag[i^1]=1;
		    	memset(vis1,0,sizeof(vis1));
		    	if(dfs2(edges[i].from,edges[i].dist)) is[i]=is[i^1]=1;
		    }
		int ans=0,answ=0;
		for(int i=0;i<edges.size();i++)
			if(!is[i]&&flag[i])
			{
				is[i]=is[i^1]=1;
			    ans++;
			    answ+=edges[i].dist;
			}
		printf("%d %d\n",ans,answ);
	}
	return 0;
}