f = open("apm.in")
# N reprezinta nr de noduri, M reprezinta nr de muchii
N,M = [int(x) for x in f.readline().split()]


culori=[0]
for i in range(1,N+1):
    culori.append(i)

def reuneste(nod_u, nod_v):
    culoare_u = culori[nod_u]
    culoare_v = culori[nod_v]
    for j in range(1,N+1):
        if culori[j]==culoare_v:
            culori[j]=culoare_u

def graf_muchii(nr_muchii):
    graf=[]
    for i in range(nr_muchii):
        x,y,w = [int(u) for u in f.readline().split()]
        pereche = (x,y,w)
        graf.append(pereche)
    return graf

graf = graf_muchii(M)
# sortare
graf = sorted(graf, key = lambda x:x[2])
cost_apcm = 0
nr_muchii_apcm = 0
lista_apcm = []
for (x,y,w) in graf:
    if culori[x]!=culori[y]:
        lista_apcm.append([x,y])
        reuneste(x,y)
        cost_apcm += w
        nr_muchii_apcm += 1
        if nr_muchii_apcm == N-1:
            break

with open("apm.out","w") as g:
    g.write(str(cost_apcm)+'\n')
    g.write(str(nr_muchii_apcm)+'\n')
    for muchie in lista_apcm:
        g.write(' '.join(map(str, muchie))+'\n')

# O(MlogN +N^2) apcm cu colorarea componentelor