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

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

def reprezentare(nod_u):
    if tata[nod_u]==0:
        return nod_u
    tata[nod_u] = reprezentare(tata[nod_u])
    return tata[nod_u]

def reuneste(nod_u, nod_v):
    reprez_u = reprezentare(nod_u)
    reprez_v = reprezentare(nod_v)
    if h[reprez_u] > h[reprez_v]:
        tata[reprez_v] = reprez_u
    else:
        tata[reprez_u] = reprez_v 
        if h[reprez_u] == h[reprez_v]:
            h[reprez_v] = h[reprez_v] + 1



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_sortat = sorted(graf, key = lambda x:x[2])
cost_apcm = 0
nr_muchii_apcm = 0
lista_apcm = []
for (x,y,w) in graf:
    if reprezentare(x)!=reprezentare(y):
        lista_apcm.append([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')