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>

using namespace std;

int par[512];

void init(int n)
{
    memset(par, -1, sizeof(par));
}

int find(int x)
{
    return (par[x] < 0 ? x : par[x] = find(par[x]));
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    
    if (x == y) return;
    
    if (-par[x] < -par[y]) swap(y, x);
    
    par[x] += par[y];
    par[y] = x;
}

bool same(int x, int y)
{
    return (find(x) == find(y));
}

struct Edge {
    int from, to, cost, id;
    
    Edge(int cost, int from, int to, int id) :
        cost(cost), from(from), to(to), id(id){}
};

bool operator < (const Edge &a, const Edge &b)
{
    return (a.cost < b.cost);
}

vector<Edge> G[512], edges, bridges;
int ehead[512];
int ord[512], low[512], vis[512];
bool done[100000];

void dfs(int v, int &k, int id)
{
    vis[v] = done[id] = true;
    ord[v] = low[v] = k++;
    
    for (int i = ehead[v]; i < G[v].size(); i++){
        if (!vis[G[v][i].to]){
            dfs(G[v][i].to, k, G[v][i].id);
            low[v] = min(low[v], low[G[v][i].to]);
        }
        else if (!done[G[v][i].id]){
            done[G[v][i].id] = true;
            low[v] = min(low[v], ord[G[v][i].to]);
        }
    }
    
    for (int i = ehead[v]; i < G[v].size(); i++){
        if (ord[v] < low[G[v][i].to]){
            bridges.push_back(G[v][i]);
        }
    }
}

int main()
{
    int N, M;
    
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back(Edge(c, a, b, i));
    }
    
    sort(edges.begin(), edges.end());
    
    init(N);
    
    for (int i = 0; i < M;){
        vector<Edge> cand;
        
        cand.push_back(edges[i++]);
        while (i < M && edges[i].cost == cand[0].cost){
            cand.push_back(edges[i++]);
        }
        
        int ncost = cand[0].cost;
        for (int j = 0; j < cand.size(); j++){
            pair<int, int> p = make_pair(cand[j].from, cand[j].to);
            int x = find(p.first), y = find(p.second);
            //if (x != y){
                G[x].push_back(Edge(ncost, x, y, cand[j].id));
                G[y].push_back(Edge(ncost, y, x, cand[j].id));
            //}
        }
        memset(ord, 0, sizeof(ord));
        memset(low, 0, sizeof(low));
        memset(vis, 0, sizeof(vis));
        
        for (int j = 0; j < cand.size(); j++){
            if (!done[cand[j].id]){
                int k = 1;
                dfs(find(cand[j].from), k, cand[j].id);
            }
            ehead[find(cand[j].from)]++;
            ehead[find(cand[j].to)]++;
        }
        
        for (int j = 0; j < cand.size(); j++){
            merge(cand[j].from, cand[j].to);
        }
    }
    
    printf("%d ", bridges.size());
    
    int s = 0;
    
    for (int i = 0; i < bridges.size(); i++){
        s += bridges[i].cost;
    }
    
    printf("%d\n", s);
    
    return (0);
}