import copy
#from collections import deque
f = open("tabutata2.txt", "r")

dictofneighbours = {}

for line in f:
    if line.split()[0] not in dictofneighbours:
        lista = []
        lista.append([line.split()[1], line.split()[2]])
        dictofneighbours[line.split()[0]] = lista
    else:
        dictofneighbours[line.split()[0]].append([line.split()[1], line.split()[2]])
    if line.split()[1] not in dictofneighbours:
        lista = []
        lista.append([line.split()[0], line.split()[2]])
        dictofneighbours[line.split()[1]] = lista
    else:
        dictofneighbours[line.split()[1]].append([line.split()[0], line.split()[2]])
f.close()

# print(dictofneighbours)

f = open("tabutata2.txt", "r")
start_node = f.read(1)
end_node = start_node

first_solution = []

visiting = start_node

distance_of_first_solution = 0

while visiting not in first_solution:
    minim = 10000
    for k in dictofneighbours[visiting]:
        if int(k[1]) < int(minim) and k[0] not in first_solution:
            minim = k[1]
            best_node = k[0]

    first_solution.append(visiting)
    distance_of_first_solution = distance_of_first_solution + int(minim)
    visiting = best_node

first_solution.append(end_node)

position = 0
for k in dictofneighbours[first_solution[-2]]:
    if k[0] == start_node:
        break
    position += 1

distance_of_first_solution = distance_of_first_solution + int(dictofneighbours[first_solution[-2]][position][1]) - 10000

# print(first_solution)
# print(distance_of_first_solution)
#print(dictofneighbours)


def findneighbours(solution):

    neighborhood_of_solutions = []

    for n in solution[1:-1]:
        idx1 = solution.index(n)
        for kn in solution[1:-1]:
            idx2 = solution.index(kn)
            if n == kn:
                continue

            _tmp = copy.deepcopy(solution)
            _tmp[idx1] = kn
            _tmp[idx2] = n

            distance = 0

            for k in _tmp[:-1]:
                next_node = _tmp[_tmp.index(k)+1]
                for i in dictofneighbours[k]:
                    if i[0] == next_node:
                        distance = distance + int(i[1])
            _tmp.append(distance)

            if _tmp not in neighborhood_of_solutions:
                neighborhood_of_solutions.append(_tmp)

    for sl in neighborhood_of_solutions:
        indexOfLastItemInTheList = len(sl)-1

    neighborhood_of_solutions.sort(key=lambda x: x[indexOfLastItemInTheList])
    return neighborhood_of_solutions


# neighborhood = findneighbours(first_solution)
# print(first_solution)
# print(neighborhood[0])


count = 1
solution = first_solution
tabu_list = []

while count <= 4:
    neighborhood = findneighbours(solution)
    index_of_best_solution = 0
    best_solution = neighborhood[index_of_best_solution]

    i = 0
    while i < len(best_solution):

        if best_solution[i] != solution[i]:
            first_exchange_node = best_solution[i]
            second_exchange_node = solution[i]
            print(first_exchange_node, second_exchange_node)
            continue

            # if [first_solution, second_exchange_node] not in tabu_list:
            #     tabu_list.append([first_exchange_node, second_exchange_node])
            #     solution = best_solution
            #     print(solution)
            # else:
            #     solution = neighborhood[index_of_best_solution+1]
            #     print(solution)

    count = count + 1
print("e")