import time
from math import *
start = time.clock()

i = open("Data5.txt")
lines = i.readlines()
i.close()

output = ''
nodes = []
prices = []

def distance(nodes,start,end,price):
    global prices
    startpoints = [node[0] for node in nodes]
    for i in range(startpoints.count(start)):
        index = startpoints.index(start)
        destination = nodes[index][1]
        price += nodes[index][2]
        print destination
        if destination == end:
            prices.append(price)
            price = 0
        else:
            distance(nodes,destination,end,price)
        nodes.pop(index)
        startpoints.pop(index)
        
for i,line in enumerate(lines[1:]):
    if len(line) > 3:
        elements = line.strip().split(' ')
        nodes.append([elements[0],elements[1],int(elements[2])])
    else:
        distance(nodes,'YYZ','SEA',0)
        output += str(min(prices))+'\n'
        print prices
        nodes = []
        prices = []
distance(nodes,'YYZ','SEA',0)
output += str(min(prices))
print prices
#print output

print "calculations took", time.clock()-start, "seconds"

o = open("OUT5.txt","w")
o.write(output)
o.close()