e=0
with open("apm.in","r") as f:
    e=[[int(x) for x in t.split()][::-1] for t in f.read().strip().split("\n")][2:]
e.sort()
s=[]
t=list(range(len(e)+9))
def g(x):
    if x==t[x]:
        return x
    t[x]=g(t[x])
    return t[x]
q=0
for x in e:
    a,b=g(x[1]),g(x[2])
    if a!=b:
        q+=x[0]
        s.append(x[1::1])
        t[a]=b
with open("apm.out","w") as f:
    import sys
    sys.stdout=f
    print(q)
    print(len(s))
    for x in s:
        print(x[0],x[1])