import sys

class Muchie:
    def __init__(self, x, y, cost):
        self.x = x
        self.y = y
        self.cost = cost

sys.stdin = open('apm.in', 'r')
sys.stdout = open('apm.out', 'w')

n, m = map(int, input().split())
gr = [] # aici se va stoca graful folosind clasa de mai sus

for _ in range(m):
    x, y, cost = map(int, input().split())
    gr.append(Muchie(x,y,cost))

tata = [0] * (n + 1)
h = [0] * (n + 1)

# def initializare(nod):
#     tata[nod] = h[nod] = 0 # nici nu era necesar

def reprez(nod):  # reprezentantul este radacina arborelui
    if tata[nod] == 0:  # este radacina
        return nod
    tata[nod] = reprez(tata[nod])  # asa se condenseaza graful (adica nu avem sub arbori de inaltimi mari
    return tata[nod]

def reuniune(nod1, nod2):
    rep1 = reprez(nod1)
    rep2 = reprez(nod2)
    if h[rep1] > h[rep2]:
        tata[rep2] = rep1
    else:
        tata[rep1] = rep2
        if h[rep1] == h[rep2]:
            h[rep2] += 1

def kruskall():
    # sortare
    def key(muchie):
        return muchie.cost
    gr.sort(key=key)

    apm = {i: [] for i in range(1, n + 1)}
    nr_muchii = 0
    cost_apm = 0
    for muchie in gr:
        if reprez(muchie.x) != reprez(muchie.y):
            # trb sa ii reunim si sa crestem nr de muchii
            reuniune(muchie.x, muchie.y)
            apm[muchie.x].append((muchie.y, muchie.cost))
            apm[muchie.y].append((muchie.x, muchie.cost))
            nr_muchii += 1
            cost_apm += muchie.cost
            if nr_muchii == n - 1:
                break

    return cost_apm, nr_muchii, apm

s = set()

cost_apm, nr_muchii, apm = kruskall()

print(cost_apm)
print(nr_muchii)

res = []
for nod in range(1, n + 1):
    for vecin, _ in apm[nod]:
        if (nod, vecin) not in s:
            res.append(f"{nod} {vecin}")
            s.add((nod, vecin))
            s.add((vecin, nod))

print('\n'.join(map(str, res)))