f=open("apm.in",'r')
w=open("apm.out",'w')

n,m=f.readline().split()
n,m=int(n),int(m)

a=[]

for _ in range(m):
    content=f.readline().split()
    x=int(content[0])
    y=int(content[1])
    z=int(content[2])
    a.append((x,y,z))

ct=0
apm=[]
parent=[i for i in range(n+1)]
rank=[0 for _ in range(n+1)]

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

def union(x,y,parent,rank):
    rootx=find(x,parent)
    rooty=find(y,parent)
    if rootx != rooty:
        if rank[rootx] > rank[rooty]:
            parent[rootx] = rooty
        elif rank[rootx] < rank[rooty]:
            parent[rooty] = rootx
        else:
            parent[rooty]=rootx
            rank[rootx] += 1
        return True
    return False

a.sort(key = lambda x : x[2])
for x,y,weight in a:
    if union(x,y,parent,rank):
        ct+=weight
        apm.append((x,y))

w.write(str(ct)+"\n")
w.write(str(len(apm))+"\n")
for x, y in apm:
    w.write(str(x)+" "+str(y)+"\n")

f.close()
w.close()