Example

Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3


Output

1 3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(N, M) = map(int, input().split())
E0 = []
for i in range(M):
	(S, D, C) = map(int, input().split())
	E0.append((C, S - 1, D - 1))
E0.sort()
(*parent,) = range(N)

def root(x):
	if x == parent[x]:
		return x
	y = parent[x] = root(parent[x])
	return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if px < py:
		parent[py] = px
	else:
		parent[px] = py
cnt = 0
base = None
for i in range(M):
	(C, S, D) = E0[i]
	if root(S) != root(D):
		unite(S, D)
		cnt += 1
		if cnt == N - 1:
			base = C
ES = {}
CM = {}
for i in range(M):
	(C, S, D) = E0[i]
	if C <= base:
		ES.setdefault(C, set()).add((S, D))
		CM[S, D] = C

def bridge(G, N):
	result = set()
	label = [None] * N
	gen = 0
	cost = [0] * N

	def dfs(u, p):
		nonlocal gen
		res = 0
		for v in G[u]:
			if v == p:
				continue
			if label[v] is not None:
				if label[v] < label[u]:
					cost[v] += 1
					res += 1
			else:
				label[v] = gen
				gen += 1
				r = dfs(v, u)
				if r == 0:
					result.add((u, v) if u < v else (v, u))
				res += r
		res -= cost[u]
		return res
	for v in range(N):
		if not label[v]:
			label[v] = gen
			gen += 1
			r = dfs(v, -1)
			assert r == 0, r
	return result
G = [[] for i in range(N)]
cnt = 0
ans = 0
for C in sorted(ES):
	for (S, D) in ES[C]:
		G[S].append(D)
		G[D].append(S)
	B = bridge(G, N)
	cnt += len(B & ES[C])
	ans += len(B & ES[C]) * C
print(cnt, ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 13
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

class UnionFind:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] <= self.table[s2]:
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2
			return True
		return False

	def subsetall(self):
		a = []
		for i in range(len(self.table)):
			if self.table[i] < 0:
				a.append((i, -self.table[i]))
		return a

def main():
	rr = []

	def f(n, m):
		ee = [LI() + [_] for _ in range(m)]
		e = sorted(ee, key=lambda x: [x[2], x[3]])
		s = []
		ns = []
		uf = UnionFind(n + 1)
		t = 0
		ttc = 0
		for (a, b, c, i) in e:
			if uf.union(a, b):
				s.append(i)
				t += c
				ttc += 1
			else:
				ns.append((a, b, c))
		r = 0
		rc = 0
		for si in s:
			tr = 0
			tc = 0
			uf = UnionFind(n + 1)
			w = ee[si][2]
			for sj in s:
				if si == sj:
					continue
				uf.union(ee[sj][0], ee[sj][1])
			sf = True
			for (a, b, c) in ns:
				if c == w and uf.union(a, b):
					sf = False
					break
			if sf:
				rc += 1
				r += w
		return '{} {}'.format(rc, r)
	while 1:
		(n, m) = LI()
		if n == 0:
			break
		rr.append(f(n, m))
		break
	return '\n'.join(map(str, rr))
print(main())