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 = [int(x) for x in f.readline().split()]
    muchii.append(linie)
f.close()

muchii_apcm = []

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

g = open("apm.out", "w")
print(cost,file=g)
print(n-1,file=g)
for x, y in muchii_apcm:
    print(x,y, file=g)
g.close()