import time
import itertools
start = time.time()
locations = {}
lengths = []
cached = {}
file = open('day9_input.txt', 'r')
for line in file:
    splits = line.split(" ")
    locations.setdefault(splits[0], {'destinations' : {} })
    locations.setdefault(splits[2], {'destinations' : {} })
    locations[splits[0]]['destinations'].setdefault(splits[2], int(splits[4]))
    locations[splits[2]]['destinations'].setdefault(splits[0], int(splits[4]))

for perm in itertools.permutations(locations):
    if perm in cached:
        continue;
    if perm[::-1] in cached:
        continue;
    cached[perm] = 1;
    length = 0
    for i in range(0, len(perm)-1):
        length += locations[perm[i]]['destinations'][perm[i+1]]
    lengths.append([length, perm])

print( min(lengths), max(lengths) )
print(time.time() - start)