class DSU:
    def __init__(self , n: int):
        self.parent = list(range(n))
        self.size = [1 for _ in range(n)]

    def find(self , x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self , x: int , y: int) -> bool:
        rx , ry = self.find(x) , self.find(y)

        if rx == ry:
            return False

        if self.size[rx] < self.size[ry]:
            rx , ry = ry , rx

        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True




with open("apm.in" , "r") as f:
    n , m = map(int , f.readline().split())
    
    edges = []
    for _ in range(m):
        u , v , w = map(int , f.readline().split())
        edges.append((u , v , w))

dsu = DSU(n)
MST = []
cost = 0
taken = 0

for u , v , w in edges:
    if dsu.union(u , v):
        cost += w
        taken += 1
        MST.append((u , v))

        if taken == n - 1:
            break


with open("apm.out" , "w") as g:
    g.write(str(cost) + "\n")
    g.write(str(taken) + "\n")
    
    for u , v in MST:
        g.write(f"{u} {v}\n")

if __name__ = "__main__"
    main()