import java.util.*;     // Scanner, Arrays
import java.io.File;
public class SortListTSP
{
   static boolean DEBUG = false;
   static Scanner console = new Scanner(System.in);

   static class Edge
   {  int length;
      int dest;
      Edge next;

      Edge(int length, int dest, Edge next)
      {  this.length = length;
         this.dest   = dest;
         this.next   = next;
      }
   }

   static String[]  name;
   static boolean[] visited;
   static Edge[]    adjList;
   static int[]     solution;
   static int       size;
   static int       totalLength;
   static boolean   VERBOSE = false;

   static int find(String city)
   {  int k;

      for (k = size-1; k >= 0; k--)
         if (city.equals(name[k]))
            break;
      return k;
   }

   static void init(Scanner inp) throws Exception
   {  int    row, col, cut;
      String lineIn, city;

      size    = inp.nextInt();  inp.nextLine();
      name    = new String[size];
      visited = new boolean[size];
      adjList = new Edge[size];

      solution = new int[size];

      for (row = 0; row < size; row++)
      {  name[row] = inp.nextLine();
         adjList[row] = new Edge(-1,0,null);     // Dummy header
      }
      inp.nextLine();

      while (inp.hasNext())
      {  lineIn = inp.nextLine();
         cut = lineIn.indexOf('"', 1);
         city = lineIn.substring(1, cut);
         lineIn =lineIn.substring(cut+1).trim();
         row = find(city);
         if (row >= 0)
         {  cut = lineIn.indexOf('"', 1);
            city = lineIn.substring(1, cut);
            lineIn =lineIn.substring(cut+1).trim();
            col = find(city);
            if (col >= 0)
            {  int length = Integer.parseInt(lineIn);
               Edge prev = adjList[row],
                    curr = prev.next;

            // Linked list "addOrdered" logic with dummy header
               while (curr != null && length > curr.length)
               {  prev = curr;  curr = prev.next;  }
               prev.next = new Edge(length, col, curr);

            // Ditto, but for [col][row] adjacency list
               prev = adjList[col]; curr = prev.next;
               while (curr != null && length > curr.length)
               {  prev = curr;  curr = prev.next;  }
               prev.next = new Edge(length, row, curr);
            }
            else
               System.out.printf("Failed to find dest. city %s\n", city);
         }
         else
            System.out.printf("Failed to find src. city %s\n", city);
      }
      if (DEBUG) dump();
   }

   static void dump()
   {  int k;

      for (k = 0; k < size; k++)
      {  Edge current = adjList[k];

         System.out.printf("%s to ", name[k]);
         while (current != null)
         {  System.out.printf("  %s", name[current.dest]);
            current = current.next;
         }
         System.out.println();
      }
   }

   static void check(int index, int[] path, int distance)
   {  if (index < size-1)    // Missed some city
         return;
      if (distance <= totalLength)
      // Requirement:  choose option with earlier 2nd city
      {  if (distance < totalLength)
         {  System.arraycopy(path, 0, solution, 0, size);
            totalLength = distance;
         }
         else if ( solution[1] > path[1] )
         {  System.arraycopy(path, 0, solution, 0, size);
            totalLength = distance;
         }
      }
   }

   static void tour(int index, int[] path, int distance)
   {  int col;
      Edge current = adjList[path[index]].next;

      if (DEBUG)
         System.out.printf("[%d] is %s\n", index, name[path[index]]);
      for ( ; current != null; current = current.next)
      {  col = current.dest;
         if (DEBUG)
         {  System.out.printf("Check %s", name[col]);
            console.nextLine();
         }
         if(visited[col])
            continue;   // already visited
         if (col == 0)  // I.e., wrap-around
         // Note:  add in the distance back to [0]
            check(index, path, distance+current.length);
         else
         {  distance += current.length;
            if (distance < totalLength)
            {  path[index+1] = col;
               visited[col] = true;
               tour(index+1, path, distance);
               visited[col] = false;
            }
            distance -= current.length;
         }

      }
   }

   static public void main(String[] args) throws Exception
   {
      String filename = args.length == 0 ? "InlandNW_27.txt"
                                         : args[0];
      Scanner input = new Scanner ( new java.io.File(filename) );
      int[]   vect;
      long begin;
      int     pass, nPasses = args.length < 2 ? 10
                            : Integer.parseInt(args[1]);

      System.out.printf("Reading from %s\n", filename);
      init(input);
      vect = new int[size];
      begin = System.nanoTime();
      for (pass = 0; pass < nPasses; pass++)
      {
         // Note:  by definition, we start at city[0];
         totalLength = Integer.MAX_VALUE;
         tour(0, vect, 0);
      }
      System.out.printf("Average time:  %3.3f milliseconds\n",
         (System.nanoTime()-begin) * 1E-06 / nPasses);
      if (totalLength == Integer.MAX_VALUE)
         System.out.println("No solution found");
      else
      {  System.out.printf("Total length:  %d\n", totalLength);
         if (VERBOSE)
         {  for (int k = 0; k < size; k++)
               System.out.println(name[solution[k]]);
            System.out.println(name[0]);
         }
      }
   }
}