parent = []
sz = []

def find(v):
    if v != parent[v]:
        parent[v] = find(parent[v])
    return parent[v]

def union(x, y):
    x = find(x)
    y = find(y)
    
    # evitam daca suntem deja in acelasi set
    if x == y:
        return False

    if sz[x] < sz[y]:
        parent[x] = y
        sz[y] += sz[x]

    else:
        parent[y] = x
        sz[x] += sz[y]

    return True

def main():
    global parent, sz
    results = []

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

        # init globale
        parent = list(range(n))
        sz = [1] * n

        egd = []
        for _ in range(m):
            x, y, cost = map(int, f.readline().split())
            egd.append((cost, x - 1, y - 1))

        # sortam dupa cost
        egd.sort()

        arb_cost = 0
        arb_edges = []

        for cost, x, y in egd:
            if union(x, y):
                # adaugam muchia in arb daca avem unire
                arb_cost += cost
                arb_edges.append((x + 1, y + 1))

                # verificam daca am terminat
                if len(arb_edges) == n - 1:
                    break
            

    with open("apm.out", "w") as out:
        out.write(str(arb_cost) + "\n")
        out.write(str(len(arb_edges)) + "\n")
        for u, v in arb_edges:
            out.write(f"{v} {u}\n")

main()