import heapq
import sys

sys.stdin = open('apm.in', 'r')
sys.stdout = open('apm.out', 'w')

n, m = map(int, input().split())
gr = { i : [] for i in range(1, n + 1) }
viz = [0] * (n + 1)
nivel = [0] * (n + 1)
start = None


for i in range(m):
    x, y, cost = map(int, input().split())
    if start is None:
        start = x
    gr[x].append((y, cost))
    gr[y].append((x, cost))


apm = { i : [] for i in range(1, n + 1)}

def prim(start):
    total_cost = 0
    nr_muchii = 0
    q = []
    for urm in gr[start]:
        heapq.heappush(q, (urm[1], start, urm[0]))  # cost nod vecin

    viz[start] = 1
    while q:
        cost, nod, vecin = heapq.heappop(q)
        print(nod, vecin)
        if viz[vecin] == 0:
            viz[vecin] = 1
            nr_muchii += 1
            total_cost += cost
            apm[nod].append(vecin)
            apm[vecin].append(nod)
            for urm in gr[vecin]:
                heapq.heappush(q,(urm[1], vecin, urm[0])) # cost nod vecin

        if nr_muchii == n - 1:
            break

    return total_cost, nr_muchii


total_cost, nr_muchii = prim(start)

print(total_cost)
print(nr_muchii)

s = set()

for nod in range(1, n + 1):
    for vecin in apm[nod]:
        if (nod, vecin) not in s:
            print(nod, vecin)
            s.add((nod, vecin))
            s.add((vecin, nod))