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 <algorithm>
using std::sort;
using std::vector;

int min(int a, int b){return (a<b)?a:b;}

const int MAXN = 500+10;
const int MAXEDGE = MAXN * MAXN;

struct edge{int u, v, c;}Edge[MAXEDGE];
bool comp(edge a, edge b){return a.c < b.c;}
vector<edge> graph[MAXN];
bool used[MAXEDGE];

int SET[MAXN];
int Find(int x){
    if(SET[x]==x) return x;
    else return SET[x] = Find(SET[x]);
}

int res=0, sum=0;
int dfs_no[MAXN];
int low[MAXN];
int dfs_time;

int Tarjan(int u,int fa, int Cost){
    low[u] = dfs_no[u] = ++dfs_time;
    for(int i=0 ; i<graph[u].size() ; i++){
        int to;
        if(graph[u][i].u == u) to = graph[u][i].v;
        if(graph[u][i].v == u) to = graph[u][i].u;
        if(to==fa || to==u) continue;
        if(dfs_no[to]) low[u] = min(low[u], low[to]);
        else{
            int lowto = Tarjan(to, u, Cost);
            if(lowto > dfs_no[u] && graph[u][i].c==Cost){
                res++;
                sum+=Cost;
            }
            low[u] = min(low[u], lowto);
        }
    }
    return low[u];
}

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    for(int i=1;i<=N;i++)
        SET[i] = i;
    for(int i=0;i<M;i++)
        scanf("%d %d %d", &Edge[i].u, &Edge[i].v, &Edge[i].c);
    sort(Edge, Edge+M, comp);
    for(int i=0 ; i<M ;){
        int cost=Edge[i].c;
        int r;
        for(r=i ; r<M && Edge[r].c==cost ; r++);
        for(int j=i ; j<r ; j++){
            int u = Edge[j].u;
            int v = Edge[j].v;
            int set1 = Find(u);
            int set2 = Find(v);
            if(set1 == set2) continue;
            graph[u].push_back(Edge[j]);
            graph[v].push_back(Edge[j]);
        }
        dfs_time=1;
        for(int j=1;j<=N;j++) low[j] = dfs_no[j] = 0;
        for(int j=1;j<=N;j++){
            if(dfs_no[j]==0) Tarjan(j, 0, cost);
        }
        for(int j=i ; j<r ; j++){
            int u = Edge[j].u;
            int v = Edge[j].v;
            int set1 = Find(u);
            int set2 = Find(v);
            if(set1 == set2) continue;
            graph[u].pop_back();
            graph[v].pop_back();
        }
        for(int j=i ; j<r ; j++){
            int u = Edge[j].u;
            int v = Edge[j].v;
            int set1 = Find(u);
            int set2 = Find(v);
            if(set1 != set2){
                graph[u].push_back(Edge[j]);
                graph[v].push_back(Edge[j]);
                SET[set1] = set2; 
            }           
        }
        i = r;
    }
    printf("%d %d\n", res, sum);
    return 0;
}