class unionf:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
rootu = self.find(u)
rootv = self.find(v)
if rootu != rootv:
if self.rank[rootu] > self.rank[rootv]:
self.parent[rootv] = rootu
elif self.rank[rootu] < self.rank[rootv]:
self.parent[rootu] = rootv
else:
self.parent[rootv] = rootu
self.rank[rootu] += 1
def kruskal(n ,map1):
map1.sort(key=lambda x: (x[2], x[3]))
uf = unionf(n)
mst = []
sumt , sumc = 0 , 0
for u , v , t ,c in map1:
if uf.find(u) != uf.find(v):
uf.union(u,v)
mst.append((u, v))
sumt += t
sumc += c
if len(mst) == n-1:
break
return sumt , sumc , mst
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
#N = 5
#M = 7
#edges = [
# (0, 1, 161, 79),
# (0, 2, 161, 15),
# (0, 3, 13, 153),
# (1, 4, 142, 183),
# (1, 4, 236, 80),
# (2, 4, 40, 241),
# (2, 1, 65, 92)
#]
sumt, sumc, mst = kruskal(N, edges)
print(sumt, sumc)
for u, v in mst:
print(u, v)
