gistfile.py

import re
from itertools import permutations

puzzle_input = """
Tristram to AlphaCentauri = 34
Tristram to Snowdin = 100
Tristram to Tambi = 63
Tristram to Faerun = 108
Tristram to Norrath = 111
Tristram to Straylight = 89
Tristram to Arbre = 132
AlphaCentauri to Snowdin = 4
AlphaCentauri to Tambi = 79
AlphaCentauri to Faerun = 44
AlphaCentauri to Norrath = 147
AlphaCentauri to Straylight = 133
AlphaCentauri to Arbre = 74
Snowdin to Tambi = 105
Snowdin to Faerun = 95
Snowdin to Norrath = 48
Snowdin to Straylight = 88
Snowdin to Arbre = 7
Tambi to Faerun = 68
Tambi to Norrath = 134
Tambi to Straylight = 107
Tambi to Arbre = 40
Faerun to Norrath = 11
Faerun to Straylight = 66
Faerun to Arbre = 144
Norrath to Straylight = 115
Norrath to Arbre = 135
Straylight to Arbre = 127
""".strip().split('\n')

cities = set()
distances = {}

for line in puzzle_input:
    left, _, right, _, distance = line.split(' ')
    distance = int(distance)
    cities.add(left)
    cities.add(right)
    distances[(left, right)] = distance
    distances[(right, left)] = distance

shortest_route = float('inf')
longest_route = float('-inf')
for route in permutations(cities):
    total_distance = 0
    for pair in zip(route, route[1:]):
        total_distance += distances[pair]
    shortest_route = min(total_distance, shortest_route)
    longest_route = max(total_distance, longest_route)

print(shortest_route)
print(longest_route)