/* Sample solution for NWERC'06: Ticket To Ride
 * Author: Per Austrin
 *
 * Algorithm: 
 * Essentially brute force.  Try all ways of partitioning the four
 * train lines together, then compute cost of a minimal steiner tree
 * on the partition.  To compute minimal steiner tree on a set of k
 * nodes, select up to k-2 of the remaining nodes (since there can be
 * at most this many internal nodes in the steiner tree) and compute a
 * minimal spanning tree on the up to 2k-2 nodes.  There are roughly
 * (n-k choose k-2) ways of choosing the k-2 nodes, which is at most
 * (22 choose 6), which is roughly 75000.
 */
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

const int inf = 1<<26;

int msts;
int n, dist[40][40];
int cityset[40], inset[40];

// Simple implementation of Prim's MST algorithm
int mst(int cities) {
  ++msts;
  int dst[40], used[40], res = 0;
  for (int i = 0; i < cities; ++i)
    dst[i] = inf, used[i] = false;
  dst[0] = 0;
  for (int i = 0; i < cities; ++i) {
    int bj = -1;
    for (int j = 0; j < cities; ++j)
      if (!used[j] && (bj == -1 || dst[j] < dst[bj]))
	bj = j;
    used[bj] = true;
    res += dst[bj];
    for (int j = 0; j < cities; ++j)
      dst[j] <?= dist[cityset[bj]][cityset[j]];
  }
  return res;
}

// Recursively choose internal nodes in the steiner tree
int steinertree(int internal, int from, int *out) {
  if (internal <= 0) return mst(out-cityset);
  int res = mst(out-cityset);
  for (int i = from; i < n; ++i) {
    if (inset[i]) continue;
    *out = i;
    res <?= steinertree(internal-1, i+1, out+1);
  }
  return res;
}

pair<int, int> routes[4];

// Compute a steiner tree on the set of routes indicated by the
// four lowest bits of left
int steinerforest(int left) {
  if (!left) return 0;
  int m = 0x10, res = 1<<28;
  while (!(left & m)) m >>= 1;
  assert(m < 0x10);
  for (int s = 0; s < m; ++s) {
    if ((left | s) == left) {
      int size = 0;
      memset(inset, false, sizeof(inset));
      for (int i = 0; i < 4; ++i)
	if ((m|s) & (1<<i)) {
	  if (!inset[routes[i].first])
	    inset[cityset[size++] = routes[i].first] = true;
	  if (!inset[routes[i].second])
	    inset[cityset[size++] = routes[i].second] = true;
	}
      int cost = steinertree(size-2, 0, cityset+size);
      res <?= cost + steinerforest(left & ~(m|s));
    }
  }
  return res;
}

int main(void) {
  int m;
  while (scanf("%d%d", &n, &m) == 2 && n) {
    map<string, int> id;
    char name1[50], name2[50];
    memset(dist, 0x1f, sizeof(dist));
    for (int i = 0; i < n; ++i) {
      scanf("%s", name1);
      id[name1] = i;
      dist[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
      int d;
      scanf("%s%s%d", name1, name2, &d);
      int a = id[name1], b = id[name2];
      dist[a][b] <?= d;
      dist[b][a] <?= d;
    }
    for (int k = 0; k < n; ++k)
      for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	  dist[i][j] <?= dist[i][k] + dist[k][j];
    for (int i = 0; i < 4; ++i) {
      scanf("%s%s", name1, name2);
      routes[i].first = id[name1];
      routes[i].second = id[name2];
    }
    fprintf(stderr, "go %d %d\n", n, m);
    int res = steinerforest(0xF);
    printf("%d\n", res);
    fprintf(stderr, "%d msts needed to be computed\n", msts);
    msts = 0;
  }
}