import sys

sys.setrecursionlimit(20000000)



def find(x):
    if x==tata[x]:
        return x
    tata[x]= find(tata[x])
    return tata[x]

def Union(x,y):
    tata[find(x)]= find(y)




if __name__ == "__main__":
    with open("apm.in", "r") as f:
        n, m = map(int, f.readline().strip().split())
        muchii=[]
        for i in range(m):
            x,y,c = map(int, f.readline().strip().split())
            muchii.append((c,(x,y)))
    muchii.sort()
    sol=[]
    cost=0
    tata= list(range(n+1))
    for muchie in muchii:
        if find(muchie[1][0]) != find(muchie[1][1]):
            Union(muchie[1][0],muchie[1][1])
            sol.append(muchie[1])
            cost+= muchie[0]
    with open("apm.out","w") as f:
        f.write(str(cost) + '\n')
        f.write(str(len(sol)) + '\n')
        for el in sol:
            f.write( str(el[0])+ ' ' + str(el[1]) + '\n')