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, 0])

    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:
    rad = x
    while rad != d[rad]:
        rad = d[rad]
    while x != rad:
        y = d[x]
        d[x] = rad
        x = y

    return rad


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

    if p != q:
        s += graf[i][2]
        graf[i][3] = 1
        Union(p, q)

with open("apm.out", "w") as f:
    f.write(f"{s}\n{n - 1}\n")
    for i in range(m):
        if graf[i][3] == 1:
            f.write(f"{graf[i][0]} {graf[i][1]}\n")