def find(parent, i):
    if parent[i-1] == i:
        return i
    return find(parent, parent[i-1])

def union(parent, rank, x, y):
     
       if rank[x-1] < rank[y-1]:
           parent[x-1] = y
       elif rank[x-1] > rank[y-1]:
           parent[y-1] = x
       else:
           parent[y-1] = x
           rank[x-1] += 1
           
def kruskal(g,n):
    sol = []
    parent = []
    rank = []
    nr_m = 0
    s = 0
    
    g.sort(key = lambda x: x[2])
    
    for i in range(1,n+1):
        parent.append(i)
        rank.append(0)
        
    c = 0
    
    while (len(sol)) < n - 1:
        u,v,w = g[c]
         
        x = find(parent,u)
        y = find(parent,v)
      
        if x != y:
            #print(e," ")
            
            c+=1
            s+=w
            nr_m+=1
            sol.append([u,v])
            union(parent, rank, x, y)
        else:
            c+=1
    with open("apm.out","w") as g:
        g.write(f"{s}\n{nr_m}\n")
        for i,j in sol:
           g.write(f"{j} {i}\n")
        

with open("apm.in") as f:
     linie = f.readline().strip().split()
     n,m = int(linie[0]), int(linie[1])
     
     g=[]
     for i in range(m):
         linie = f.readline().strip().split()
         x=[int(linie[0]), int(linie[1]), int(linie[2])]
         g.append(x)
         
     kruskal(g,n)