class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight

    def __str__(self):
        return f"({self.u},{self.v},{self.weight})"
        
    def __lt__(self, other):
        return self.weight <= other.weight
        
    def __eq__(self, other):
        self.weight == other.weight

edges = [
    Edge(1, 5, 4),
    Edge(1, 2, 2),
    Edge(1, 4, 1),
    Edge(2, 1, 2),
    Edge(2, 4, 3),
    Edge(2, 3, 3),
    Edge(2, 6, 7),
    Edge(3, 2, 3),
    Edge(3, 6, 8),
    Edge(3, 4, 5),
    Edge(4, 1, 1),
    Edge(4, 2, 3),
    Edge(4, 3, 5),
    Edge(4, 5, 9),
    Edge(5, 1, 4),
    Edge(5, 4, 9),
    Edge(6, 2, 7),
    Edge(6, 3, 8)
]


def make_set(v):
    parent[v] = v
    rank[v] = 0


def find_set(v):
    if v == parent[v]:
        return v
    parent[v] = find_set(parent[v])
    return parent[v]

def union_sets(a, b):
    a, b = find_set(a), find_set(b)
    if a != b:
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a;
        if rank[a] == rank[b]:
            rank[a] += 1

edges.sort(key=lambda e:e.weight)
pts = range(1, 7)
n = len(pts)

res = []
cost = 0
parent = {}
rank = {}
for i in range(n):
    make_set(pts[i])

for edge in edges:
    if find_set(edge.u) != find_set(edge.v):
        cost += edge.weight;
        res.append(edge);
        union_sets(edge.u, edge.v)

print('\n'.join(map(str, res)))
print(sum(e.weight for e in res))