/*
  [NWERC'06] TICKET TO RIDE
  by: Jan Kuipers
*/

using namespace std;

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>

int N,M,nextID;
map<string,int> IDcache;
vector<vector<int> > next,len;
vector<int> bit;

int ID(string s) {
  if (IDcache.count(s)) return IDcache[s];
  return IDcache[s]=nextID++;
}

int read () {
  cin>>N>>M;
  if (N==0 && M==0) return 0;

  string city;
  for (int i=0; i<N; i++) cin>>city;
  
  next=len=vector<vector<int> >(N);
  nextID=0;
  IDcache.clear();

  for (int i=0; i<M; i++) {
    string city1,city2;
    int L;
    cin>>city1>>city2>>L;
    int n1=ID(city1), n2=ID(city2);
    next[n1].push_back(n2);
    len [n1].push_back(L);
    next[n2].push_back(n1);
    len [n2].push_back(L);
  }

  bit=vector<int>(N,0);
  
  for (int i=0; i<8; i++) {
    string city;
    cin>>city;
    bit[ID(city)]|=1<<i;
  }
  
  return 1;
}

struct state { int n, mask, dist; };

bool operator < (state a, state b) {
  return a.dist > b.dist;
}

int solve () {

  vector<vector<int> > seen(N, vector<int>(1<<8, 0));
  vector<vector<int> > best(N, vector<int>(1<<8, INT_MAX/2));
  priority_queue<state> pq;
  
  for (int i=0; i<N; i++) {
    state s;
    s.n = i;
    s.mask = bit[i];
    s.dist = 0;
    pq.push(s);
    best[s.n][s.mask]=0;
  }

  while (!pq.empty()) {
    state s=pq.top(); pq.pop();
    int n=s.n, mask=s.mask, dist=s.dist;
    if (seen[n][mask]) continue;
    seen[n][mask]=1;
    //    printf ("%i/%i -> %i\n",n,mask,dist);
    for (int i=0; i<next[n].size(); i++) {
      int x = next[n][i];
      for (int m=0; m<1<<8; m++)
	if (seen[x][m]) {
	  s.mask = mask | m | bit[x];
	  s.dist = dist + best[x][m] + len[n][i];
	  s.n = n;
	  if (best[s.n][s.mask]>s.dist) { best[s.n][s.mask]<?=s.dist; pq.push(s); }
	  s.n = x;
	  if (best[s.n][s.mask]>s.dist) { best[s.n][s.mask]<?=s.dist; pq.push(s); }
	}
    }
  }

  int res = INT_MAX;

  vector<int> ii(4);
  for (ii[0]=0; ii[0]<4; ii[0]++)
    for (ii[1]=0; ii[1]<4; ii[1]++)
      for (ii[2]=0; ii[2]<4; ii[2]++)
	for (ii[3]=0; ii[3]<4; ii[3]++) {
	  int tmp=0;
	  for (int i=0; i<4; i++) {
	    int mask=0;
	    for (int j=0; j<4; j++)
	      if (ii[j]==i) mask|=3<<2*j;
	    if (mask==0) continue;
	    int tmp2=INT_MAX/10;
	    for (int n=0; n<N; n++)
	      if (best[n][mask]!=-1)
		tmp2<?=best[n][mask];
	    tmp+=tmp2;
	  }
	  res<?=tmp;
	}

  return res;
}

int main () {

  while (read()) cout<<solve()<<endl;  
  return 0;
}