import sys

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

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

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))

# sortare
def key(muchie):
    return muchie.cost

gr.sort(key=key)

apm = { i : [] for i in range(1, n + 1)}
tata = [0] * (n + 1)
h = [0] * (n + 1)
reprez = [0] * (n + 1)

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

nr_muchii = 0
cost_apm = 0

for muchie in gr:
    if reprez(muchie.x) != reprez(muchie.y):
        reuniune(muchie.x, muchie.y)
        apm[muchie.x].append(muchie.y)
        apm[muchie.y].append(muchie.x)
        nr_muchii += 1
        cost_apm += muchie.cost
        if nr_muchii == n - 1:
            break

print(cost_apm)
print(nr_muchii)
for nod in range(1, n + 1):
    for vecin in apm[nod]:
        print(nod, vecin)