#!/usr/bin/python

cities = {}

def addcity(fr, to, len):
  city = cities.get(fr, {});
  if not city.has_key(to):
    city[to] = len
    cities[fr] = city

def findShortestRoute(fr, to):
  options = {fr : 0} #you can get from fr to fr with 0 cars
  #we'll assume that 20 hops gets us anywhere on the map
  for i in range(20):
    #make new route options
    newopts = {}
    for city in options:
      lensofar = options[city]
      for tocity in cities[city]:
        tclen = cities[city][tocity]
        oldlen = options.get(tocity, 99999)
        if oldlen > tclen + lensofar:
          newopts[tocity] = tclen + lensofar
    for n in newopts:
      options[n] = newopts[n]

  return options[to]

    


fr = None
for line in open("routes.txt"):
  if line.strip() == "":
    fr = None
    continue
  if fr == None:
    fr = line.strip()
    continue
  to, length = line.split()
  length = int(length)
  addcity(fr, to, length)
  addcity(to, fr, length)


readyroutes = []

def getstr(c1, c2):
  return c1.title()+"\n"+c2.title()+"\n"+str(shortest)

for c1 in cities:
  for c2 in cities:
    shortest = findShortestRoute(c1, c2)
    if shortest < 5 or cities[c1].has_key(c2):
      continue
    if (readyroutes.count(getstr(c2, c1)) == 0):
      readyroutes.append(getstr(c1,c2))


readyroutes.sort(lambda a, b: int(a.split()[2]) - int(b.split()[2]))

for r in readyroutes:
  print r+"\n\n"

print "route amount:", len(readyroutes)