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 <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Union_Find_Tree{
	public:
	int n;
	vi Par;
	Union_Find_Tree(int n){
		Par=vi(n);
		for(int i=0;i<n;i++) Par[i]=i;
	}
	int Find_Par(int x){
		if(Par[x]==x) return x;
		return Par[x]=Find_Par(Par[x]);
	}
	bool Unite(int x,int y){
		x=Find_Par(x);
		y=Find_Par(y);
		if(x==y) return 0;
		Par[x]=y;
		return 1;
	}
	bool Same(int x,int y){
		return Find_Par(x)==Find_Par(y);
	}
};

class Graph{
	private:
	int n,t=0,id=0;
	vvp g;
	vi dis,low,par;
	vp br;
	void DFS(int v,int k,int pre){
		dis[v]=low[v]=k;
		for(auto p:g[v]){
			int u=p.first,I=p.second;
			if(!dis[u]){
				par[u]=v;
				DFS(u,k+1,I);
				low[v]=min(low[v],low[u]);
				if(dis[v]<low[u]) t++;
			}
			else if(I!=pre) low[v]=min(low[v],dis[u]);
		}
	}
	public:
	int Bridge(){
		dis=low=par=vi(n);
		for(int i=0;i<n;i++) if(!dis[i]) DFS(i,1,-1);
		return t;
	}
	Graph(int v){
		n=v;
		g=vvp(v);
	}
	void add_edge(int s,int t){
		g[s].push_back({t,id});
		g[t].push_back({s,id++});
	}
};

const int M=10001;
int n,m;
vi s[M],t[M];

int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,c;
		cin>>u>>v>>c;
		s[c].push_back(u-1);
		t[c].push_back(v-1);
	}
	Union_Find_Tree uft(n);
	int A=0,B=0;
	for(int i=0;i<M;i++){
		int cnt=0;
		map<int,int> mp;
		for(int j=0;j<s[i].size();j++){
			int u=uft.Find_Par(s[i][j]),v=uft.Find_Par(t[i][j]);
			if(u==v) continue;
			if(mp.find(u)==mp.end()) mp[u]=cnt++;
			if(mp.find(v)==mp.end()) mp[v]=cnt++;
		}
		if(!cnt) continue;
		Graph g(cnt);
		for(int j=0;j<s[i].size();j++){
			int u=uft.Find_Par(s[i][j]),v=uft.Find_Par(t[i][j]);
			u=mp[u];v=mp[v];
			g.add_edge(u,v);
		}
		int N=g.Bridge();
		A+=N;
		B+=N*i;
		for(int j=0;j<s[i].size();j++) uft.Unite(s[i][j],t[i][j]);
	}
	cout<<A<<' '<<B<<endl;
}