'''
 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 = []

coada_normala = []#aici vom tine muchiile care ne intereseaza la pasul curent
#"ne intereseaza" adica ele unesc multimea de noduri rezolvate cu multimea de noduri nerezolvate
#si trebuie sa alegem cea mai mica muchie din aceasta multime (coada) de muchii

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

    for i in range(len(L[1])):
        coada_normala.append((1,L[1][i][0], L[1][i][1]  ))

    muchii_adaugate = 0
    while muchii_adaugate<N-1:
        #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

        '''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
        '''
        muchie_minima = (-1, -1, 2000000000)  # (nod1, nod2, cost)
        for i in range(len(coada_normala)):
            muchie = coada_normala[i]
            print("\tmuchie = ", muchie)
            if muchie_minima[2] > muchie[2] and viz[muchie[1]]==False:
                muchie_minima = muchie

        muchii_sol.append( (muchie_minima[0], muchie_minima[1]) )
        suma_APM += muchie_minima[2]
        nod_nou = muchie_minima[1]
        print("nod_nou = ", nod_nou)
        print("muchie minima = ", muchie_minima, "\n\n")
        #adaug in coada_normala toti vecinii lui nod_nou care nu sunt vizitati
        #"nevizitati" = nu sunt inca in multimea nodurilor rezolvate (multimea rosie)
        print("caut vecinii nodului nou")
        for i in range(len(L[nod_nou])):
            muchie = L[nod_nou][i]
            if viz[muchie[0]]==False:
                coada_normala.append( ( nod_nou,  muchie[0], muchie[1]) )
        viz[nod_nou] = True
        q.append(nod_nou)
        muchii_adaugate+=1
        print("vectorul viz:")
        for i in range (0, 10):
            print("viz[", i, "] = ", viz[i])

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