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 = set()
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))


def prim(start):
    apm = {i: [] for i in range(1, n + 1)}
    total_cost = 0
    pq = []
    for urm, cur_cost in gr[start]:
        heapq.heappush(pq, (cur_cost, start, urm))  # cost nod vecin

    viz.add(start)
    while pq and len(viz) < n:
        cost, nod, vecin = heapq.heappop(pq)
        if vecin not in viz:
            viz.add(vecin)
            total_cost += cost
            apm[nod].append((vecin, cost))
            apm[vecin].append((nod, cost))
            for urm, cur_cost in gr[vecin]:
                if urm not in viz:
                    heapq.heappush(pq,(cur_cost, vecin, urm)) # cost nod vecin

    return total_cost, len(viz) - 1, apm


total_cost, nr_muchii, apm = 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))