def initial(u):
        tata[u]=h[u]=0

def reprez(u):
     if tata[u]==0:
         return u
     tata[u]=reprez(tata[u])
     return tata[u]


#reuniune ponderata - dupa inaltimea h
def reuneste(u,v):
    ru=reprez(u)
    rv=reprez(v)
    if h[ru]>h[rv]:
        tata[rv]=ru
    else:
        tata[ru]=rv
        if h[ru]==h[rv] :
            h[rv]=h[rv]+1




def kruskal( ):


    global tata,h,cost
    tata=[0]*(n+1)
    h=[0]*(n+1)
    

    for v in range(1,n+1):
        initial(v)
  
    nrmsel=0
    mc=0


    muchii.sort(key=lambda x:x[2])

    for mc in muchii:

        u=mc[0]
        v=mc[1]
        if reprez(u)!=reprez(v):
            nrmsel+=1
            muchii_apcm.append((mc[0],mc[1]))
            cost += mc[2]
            reuneste(u,v)
            if nrmsel==n-1:
                break


   


f=open("apm.in")

n, m = (int(x) for x in f.readline().split())

muchii = []

# graf- memorat ca lista de muchii
for i in range(0, m):
     linie = f.readline().split()
     muchii.append((int(linie[0]), int(linie[1]), int(linie[2])))
f.close()

muchii_apcm = []

tata=None
h=None
cost=0
kruskal()

g=open("apm.out","w")
g.write(f"{cost}")
g.write("\n")
g.write(str(n-1))
g.write("\n")
for x,y in muchii_apcm:
    g.write(f"{x} {y}\n")
g.close()