'''
 Se da un graf neorienteat, un nod sursa si un nod destinatie.
 Afisati distanta minima de la sursa la destinatie, dar si
 nodurile drumului minim de la sursa la destinatie.
'''

L = []

for i in range(1,100001):
    L.append([])#intial niciun nod nu are vecini
viz = [False] * 100001#o metoda mai simpla de a initializa
#Citirea este aproximativ la fel cu cea de la BFS si DFS
with open('apm.in') as f:
    N, M = [int(x) for x in next(f).split()]#N = numarul de noduri, M = numarul de muchii, S = Sursa, D =destinatie
    array = []
    for line in f:  # read rest of lines
        linie = [int(x) for x in line.split()]
        x = linie[0]
        y = linie[1]#acum urmeaza sa trasam o muchie
        w = linie[2]
        L[x].append((y, w))#il adaug pe y la lista de vecini a lui x
        L[y].append((x, w))#il adaug pe x la lista de vecini a lui y




q = []#q vine de la queue, care inseamna coada
dist = [-1]*100001#initial nu am ajuns la niciun nod
precedent = [0]*100001#vreau ca pentru fiecare nod sa stiu de unde am venit

'''def BFS():
    dist[S] = 0#distanta de la nodul de start la el insusi este 0
    q.append(S)
    while q!=[]:#cat timp coada nu este vida
        x = q.pop(0)
        for vecin_x in L[x]:#parcurgem toti vecinii lui x
            if dist[vecin_x]==-1:#am gasit un vecin pe care nu l-am vizitat niciodata pana acum
                dist[vecin_x] = dist[x]+1
                precedent[vecin_x] = x
                q.append(vecin_x)
'''

muchii_sol = []

#q este multimea de noduri "rezolvate"

def Prim():
    suma_APM = 0
    #intotdeauna la algoritmul Prim vom porni de la un nod oarecare
    #noi vom porni de la nodul 1
    dist[1] = 0
    viz[1] = True
    q.append(1)
    while len(q)<N:
        #la un pas, incercam sa adaugam inca un nod la multimea de noduri rezolvate
        #si implicit si muchia care uneste acel nod de multimea actuala de noduri rezolvate
        muchie_minima = (-1, -1, 2000000000)# (nod1, nod2, cost)
        for i in range(0, len(q)):
            x = q[i]
            for vecin_x in L[x]:
                muchie_curenta = (x, vecin_x[0], vecin_x[1])
                #print("muchie_curenta = ", muchie_curenta, "\n")
                if muchie_curenta[2] < muchie_minima[2] and viz[vecin_x[0]]==False:
                    muchie_minima = muchie_curenta
        muchii_sol.append( (muchie_minima[0], muchie_minima[1]) )
        suma_APM += muchie_minima[2]
        nod_nou = muchie_minima[1]
        viz[nod_nou] = True
        q.append(nod_nou)
    return suma_APM


#Apelam functia Prim

suma_APM = Prim()#Prim pune in lista muchii_sol toate muchiile ce vor face parte din APM


print("asa")
f = open("apm.out", "w")
f.write(str(suma_APM) + "\n")
f.write(str(N-1) + "\n")
for i in range(N-1):
    f.write(str(muchii_sol[i][0]) +  " " + str(muchii_sol[i][1]) + "\n" )
f.close()