#!/usr/bin/env python3

import collections, sys

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

with open('apm.in', 'r') as f:
    readInts = lambda: map(int, f.readline().split())

    N, M = tuple(readInts())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        A, B, C = tuple(readInts())
        edges[A - 1].append((B - 1, C))
        edges[B - 1].append((A - 1, C))

    D, P, h, H, PRT = [sys.maxsize] * N, list(range(N)), list(range(N)), N, [None] * N
    D[0] = 0

    def hpop():
        global H
        H -= 1
        h[0], h[H] = h[H], h[0]
        P[h[0]], P[h[H]] = 0, -1

        idx = 0
        while True:
            minIdx = idx
            if idx * 2 + 1 < H and D[h[idx]] > D[h[idx * 2 + 1]]:
                minIdx = idx * 2 + 1
            if idx * 2 + 2 < H and D[h[minIdx]] > D[h[idx * 2 + 2]]:
                minIdx = idx * 2 + 2
            if minIdx != idx:
                h[idx], h[minIdx] = h[minIdx], h[idx]
                P[h[idx]], P[h[minIdx]] = idx, minIdx
                idx = minIdx
            else:
                break
        
        return h.pop()

    def hup(idx):
        while idx > 0:
            pIdx = (idx - 1) // 2
            if D[h[idx]] < D[h[pIdx]]:
                h[idx], h[pIdx] = h[pIdx], h[idx]
                P[h[idx]], P[h[pIdx]] = idx, pIdx
                idx = pIdx
            else:
                break

    for _ in range(N):
        node = hpop()
        for B, C in edges[node]:
            if C < D[B]:
                D[B] = C
                if P[B] >= 0: PRT[B] = (node, C)
                hup(P[B])

    print(sum(prt[1] for i, prt in enumerate(PRT) if i > 0))
    print(N - 1)
    for i, prt in enumerate(PRT):
        if not i: continue
        print(f'{prt[0] + 1} {i+1}')