from typing import List

with open("apm.in", "r") as f:
    n, m = map(int, f.readline().split())
    graf = []

    for i in range(m):
        x, y, c = map(int, f.readline().split())
        graf.append((x, y, c))

    graf.sort(key=lambda x: x[2])

h: List[int] = [0 for _ in range(n + 1)]
d: List[int] = [i for i in range(n + 1)]


def Union(x: int, y: int):
    if h[x] > h[y]:
        d[y] = x
    else:
        d[x] = y
        if h[x] == h[y]:
            h[y] += 1


def Find(x: int) -> int:
    r, y = x, x
    t: int
    while r != d[r]:
        r = d[r]
    while y != r:
        t = d[y]
        d[y] = r
        y = t

    return r


s = 0
sol = []
for i in range(m):
    p = Find(graf[i][0])
    q = Find(graf[i][1])

    if p != q:
        s += graf[i][2]
        sol.append(f"{graf[i][1]} {graf[i][0]}\n")
        Union(p, q)

with open("apm.out", "w") as f:
    f.write(f"{s}\n{n - 1}\n")
    f.write("".join(sol))