def citire_matrice_cost(nume_fisier):
    fisier = open(nume_fisier, "r")
    n, m = [int (x) for x in fisier.readline().split()]
    w = [[float("inf") for i in range(n+1)] for j in range(m+1)]
    for i in range(1,n+1):
        w[i][i] = 0
    for linie in fisier:
        x, y, c = (int(x) for x in linie.split())
        w[x][y] = w[y][x] = c
    fisier.close()
    return n, m, w

def minim(d,viz):
    u = -1
    dmin = float("inf")
    for i in range (1, n+1):
        if viz[i] == 0 and d[i] < dmin:
            u = i
            dmin = d[i]
    return u

def prim(s):
    viz = [0]*(n+1)
    tata = [0]*(n+1)
    d = [float("inf")]*(n+1)

    d[s] = 0
    suma = 0
    for i in range(n):
        u = minim(d, viz)
        if (u!=1):
            suma += w[tata[u]][u]
        viz[u] = 1
        for v in range(1, n+1):
            if viz[v] == 0 and (w[u][v]<float("inf")):
                if d[v] > w[u][v]:
                    d[v] = w[u][v]
                    tata[v] = u

    print(suma)
    print(n-1)
    for u in range(1,n+1):
        if tata[u]!=0:
            print(u,tata[u])

n,m,w = citire_matrice_cost("apm.in")
prim(1)