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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct UnionFind {
  int parent[600];
  UnionFind() { memset(parent, -1, sizeof(parent)); }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) { return false; }
    if (parent[y] < parent[x]) { swap(x, y); }
    parent[x] += parent[y];
    parent[y] = x;
    return true;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
};

typedef int Weight;
struct Edge {
  int src;
  int dest;
  Weight weight;
  Edge() {;}
  Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const Edge &rhs) const {
    if (weight != rhs.weight) { return weight < rhs.weight; }
    if (src != rhs.src) { return src < rhs.src; }
    return dest < rhs.dest;
  }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int n, m;
UnionFind ufind;
Edge edges[100000];

int main() {
  while (scanf("%d %d", &n, &m) > 0) {
    REP(i, m) {
      int s, t, c;
      scanf("%d %d %d", &s, &t, &c);
      s--; t--;
      edges[i] = Edge(s, t, c);
    }
    vector<int> candidate;
    sort(edges, edges + m);
    ufind = UnionFind();
    int sum = 0;
    REP(i, m) {
      if (ufind.unionSet(edges[i].src, edges[i].dest)) {
        candidate.push_back(i);
        sum += edges[i].weight;
      }
    }
    int ans_cnt = 0;
    int ans_cost = 0;
    if (-ufind.parent[ufind.root(0)] == n) {
      REP(iter, n - 1) {
        int c = candidate[iter];
        int cnt = 1;
        int lsum = 0;
        ufind = UnionFind();
        REP(i, m) {
          if (i == c) { continue; }
          if (ufind.unionSet(edges[i].src, edges[i].dest)) {
            lsum += edges[i].weight;
            cnt++;
          }
        }
        if (sum != lsum || cnt != n) { 
          ans_cnt++;
          ans_cost += edges[c].weight;
        }
      }
    }
    printf("%d %d\n", ans_cnt, ans_cost);
  }
}