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 <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
using namespace std;

//7:10
//
//#define REP(i,n) for(int i=0;i<(int)n;++i)
//#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
//#define ALL(c) (c).begin(), (c).end()
//
//typedef int Weight;
//struct Edge {
//  int src, dst;
//  Weight weight;
//  Edge(int src, int dst, Weight weight) :
//      src(src), dst(dst), weight(weight) { }
//};
//bool operator < (const Edge &e, const Edge &f) {
//  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
//  e.src != f.src ? e.src < f.src : e.dst < f.dst;
//}
//typedef vector<Edge> Edges;
//typedef vector<Edges> Graph;
//
//typedef vector<Weight> Array;
//typedef vector<Array> Matrix;
//
//#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
//Weight maximumFlow(const Graph &g, int s, int t) {
//  int n = g.size();
//  Matrix flow(n, Array(n)), capacity(n, Array(n));
//  REP(u, n) for (auto e = g[u].begin(); e != g[u].end();++e)capacity[e->src][e->dst] += e->weight;
//
//  Weight total = 0;
//  while (1) {
//      queue<int> Q; Q.push(s);
//      vector<int> prev(n, -1); prev[s] = s;
//      while (!Q.empty() && prev[t] < 0) {
//          int u = Q.front(); Q.pop();
//          for (auto e = g[u].begin(); e != g[u].end(); ++e) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
//              prev[e->dst] = u;
//              Q.push(e->dst);
//          }
//      }
//      if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
//      Weight inc = 999999999;
//      for (int j = t; prev[j] != j; j = prev[j])
//          inc = min(inc, RESIDUE(prev[j], j));
//      for (int j = t; prev[j] != j; j = prev[j])
//          flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
//      total += inc;
//  }
//  return total;
//}
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()


const int mod = 1000000007;

struct Mod {
	long long int num;
	Mod() : num(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) { ; }
	operator long long int() { return num; }
};

Mod operator+(Mod a, Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator-(Mod a, Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator*(Mod a, Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator+=(Mod &a, Mod b) { return a = a + b; }
Mod operator-=(Mod &a, Mod b) { return a = a - b; }
Mod operator*=(Mod &a, Mod b) { return a = a * b; }
Mod operator^(Mod a, int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod inv(Mod a) { return a ^ (mod - 2); }
Mod operator/(Mod a, Mod b) { return a * inv(b); }

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	REP(i, MAX_N - 1) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(int a, int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}

long long int memo[20];//nけた

long long int powint(long long int a, int b) {
	if (b == 0)return 1;
	if (b == 1)return a;
	else {
		long long int ans = 1;
		long long int c = powint(a, b / 2);
		ans *= c*c;
		ans *= (b % 2) ? a : 1;
		return ans;
	}

}


int backnum[100000][20];

struct Node {
	Node(int aid) :children(), ancs() {
		id = (aid);
		for (int i = 0; i < 20; ++i) {
			ancs[i] = -1;
		}
	}
	int id;
	vector<int>children;
	array<int, 20>ancs;
};

struct Edge {
	int from;
	int id;
	int to;
	int cost;
};

struct nEdge {
	int from;
	int id;
	int to;
	int time;
	nEdge(const Edge e) {
		from = e.from;
		id = e.id;
		to = e.to;
		time = e.cost;
	}
	nEdge(int af, int aid, int ato, int ati) {
		from = af;
		id = aid;
		to = ato;
		time = ati;
	}
};
class Compare {
public:
	bool operator()(const nEdge& l, const nEdge& r) {
		return l.time > r.time;
	}
};
vector < vector<Edge>> Edges;



int main()
{
	int N, M;
	cin >> N >> M;
	vector<int>time(2 * M);
	Edges.resize(N);
	for (int i = 0; i < M; ++i) {
		int s, d, c;
		cin >> s >> d >> c;
		s--; d--;
		time[2 * i] = c;
		time[2 * i + 1] = c;;
		Edges[s].push_back(Edge{ s,2 * i, d, c });
		Edges[d].push_back(Edge{ d,2 * i + 1, s, c });
	}

	vector<int> ansid;
	int baseanstime = 0;
	{
		priority_queue<nEdge, vector<nEdge>, Compare> qu;
		for (int i = 0; i < Edges[0].size(); ++i) {
			qu.push(nEdge(Edges[0][i]));
		}
		vector<bool> selected(2 * M, false);
		vector<bool> go(N, false);
		go[0] = true;
		while (!qu.empty()) {
			nEdge ne(qu.top());
			qu.pop();

			if (go[ne.to]) {
				continue;
			}
			else {
				go[ne.to] = true;
				selected[ne.id] = true;
				ansid.emplace_back(ne.id);
				baseanstime += ne.time;
			}

			for (int i = 0; i < Edges[ne.to].size(); ++i) {
				qu.emplace(ne.to, Edges[ne.to][i].id, Edges[ne.to][i].to, Edges[ne.to][i].cost);
			}
		}
	}
	int answernum = 0;
	int answertime = 0;
	{
		for (int l = 0; l < ansid.size(); ++l) {
			int taiouid = (ansid[l]% 2) ? ansid[l]- 1 : ansid[l] + 1;
			assert(ansid.size() == N - 1);
			priority_queue<nEdge, vector<nEdge>, Compare> qu;
			for (int i = 0; i < Edges[0].size(); ++i) {
				qu.push(nEdge(Edges[0][i]));
			}
			int thisanstime = 0;
			vector<bool> go(N, false);
			go[0] = true;
			int c = 1;
			while (!qu.empty()) {
				if (c == N)break;
				nEdge ne(qu.top());
				qu.pop();
				
				if (go[ne.to] || ne.id == ansid[l] || ne.id == taiouid) {
					continue;
				}
				else {
					go[ne.to] = true;
					thisanstime += ne.time;
					c++;
				}

				for (int j = 0; j < Edges[ne.to].size(); ++j) {
					if (go[Edges[ne.to][j].to] || Edges[ne.to][j].id == ansid[l] || Edges[ne.to][j].id == taiouid) {
						
					}
					else {
						qu.emplace(ne.to, Edges[ne.to][j].id, Edges[ne.to][j].to, Edges[ne.to][j].cost);
					}
					
				}
			}
			if (thisanstime == baseanstime) {
				bool flag = true;
				for (int i = 0; i < go.size(); ++i) {
					if (go[i] = false)flag = false;
				}
				if (flag) {
					answernum++;
				}
			}
			else {
				answertime += time[ansid[l]];
			}
		}

	}

	cout << N - 1 - (answernum) << " " << answertime << endl;

	return 0;
}