import sys

sys.setrecursionlimit(200000)

parent, rank = [], []

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

def union(i, j):
    root_i = find(i)
    root_j = find(j)
    if root_i != root_j:
        if rank[root_i] < rank[root_j]:
            parent[root_i] = root_j
        elif rank[root_i] > rank[root_j]:
            parent[root_j] = root_i
        else:
            parent[root_i] = root_j
            rank[root_j] += 1
        return True
    return False

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])

    mst_cost = 0
    mst_edges = []
    mst_count = 0

    for u, v, cost in edges:
        if union(u, v):
            mst_cost += cost
            mst_edges.append((u, v))
            mst_count += 1
            if mst_count == n - 1:
                break
    
    return mst_cost, mst_edges

def main():
    try:
        fin = open("apm.in", "r")
        fout = open("apm.out", "w")
        input_data = fin.read().split()
    except FileNotFoundError:
        input_data = sys.stdin.read().split()
        fout = sys.stdout

    iterator = iter(input_data)

    try:
        n = int(next(iterator))
        m = int(next(iterator))

        global parent, rank
        parent = list(range(n + 1))
        rank = [0] * (n + 1)

        edges = []
        for _ in range(m):
            u = int(next(iterator))
            v = int(next(iterator))
            c = int(next(iterator))
            edges.append((u, v, c))

        mst_cost, mst_edges = kruskal(n, edges)

        fout.write(f"{mst_cost}\n")
        fout.write(f"{len(mst_edges)}\n")
        for u, v in mst_edges:
            fout.write(f"{u} {v}\n")

    except StopIteration:
        pass
    finally:
        if fout != sys.stdout:
            fin.close()
            fout.close()

if __name__ == "__main__":
    main()