import java.util.*;
import java.io.*;
import java.awt.Point;

class IndexMapper {
    ArrayList<String>  _itos = new  ArrayList<String>();
    Map<String,Integer> _stoi = new HashMap<String,Integer>();
    int _n=0;
    String str(int i) { if (i<0 || i>=_n) return null; return _itos.get(i); }

    int index(String s) {
	Integer ix = _stoi.get(s);
	if (ix != null){
	    return ix.intValue();
	}
	_stoi.put(s,_n);
	_itos.add(s);
	return _n++;
    }
    
}

public class ticket_mg {
    static final int INF = 1<<29;
    static Scanner in = new Scanner(System.in);
    IndexMapper im = new IndexMapper();
    int n,m;
    int[][] a;
    int[] mStF = new int[16];
    int[] mStT = new int[16];

    boolean[] used;

    public static void main(String[] as) throws IOException
    {
	while( new ticket_mg().solve() );
    }

    boolean solve() throws IOException
    {
	n=in.nextInt();
	m=in.nextInt();
	if (n+m==0) return false;
	for (int i=0; i<n; ++i)
	    im.index(in.next());
	a = new int[n][n];
	for (int i=0; i<n; ++i) {
	    for (int j=0; j<n; ++j)
		a[i][j]=INF;
	    a[i][i]=0;
	}
	for (int i=0; i<m; ++i) {
	    int s = im.index(in.next());
	    int t = im.index(in.next());
	    int c = in.nextInt();
	    a[t][s]=a[s][t] = Math.min(a[s][t],c);
	}
	for (int i=0;i<n;++i)
	    for (int s=0;s<n;++s)
		if (a[s][i] != INF)
		    for (int t=0;t<n;++t)
			a[s][t] = Math.min(a[s][t],a[s][i]+a[i][t]);

	for (int i=0; i<n; ++i) 
	    for (int j=0; j<n; ++j)
		if(a[i][j]==INF)
		    System.err.println("Cannot get from " 
				       +im.str(i) + " to "
				       +im.str(j));

	Point[] xy = new Point[4];
	used = new boolean[n];

	for (int i=0; i<4; ++i) {
	    
	    int x=im.index(in.next());
	    int y=im.index(in.next());
	    // System.err.println(im.str(x)+ " " + im.str(y));
	    xy[i]=new Point(x,y);
	    used[xy[i].x]=true;
	    used[xy[i].y]=true;
	}
	for (int i=1; i<16; ++i) mStT[i]=mStF[i]=INF;
	System.out.println(minSteinerForest(xy,15));
	return true;
   }

    int minSteinerForest(Point[] xy, int subset) {
	if (mStF[subset] == INF) {
	    // System.err.println("Start forrest " + subset );
	    int best=INF;
	    int m = 1<<3;
	    while (m>subset) m>>=1;
	    for ( ; m<=subset; ++m) {
		if ((m&subset)==m)
		    best = 
			Math.min(best, 
				 minSteinerTree(xy,m)
				 +minSteinerForest(xy,subset-m));
	    }
	    mStF[subset]=best;
	    /*
	    System.err.print("Done forrest " + subset + " :  ");
	    System.err.println(best);
	    */
	}
	return mStF[subset];
    }

    int minSteinerTree(Point[] xy, int subset) {
	if (mStT[subset] == INF) {
	    //System.err.print("tree " + subset + " :  ");
	    int[] v = new int[20]; // vertices in MST (max 8+6)
	    boolean[] v_aux = new boolean[n]; 
	    int nv=0;
	    int best = INF;
	    for (int i=0; i<4; ++i)
		if ((subset&(1<<i))!=0) 
		    v_aux[xy[i].x] = v_aux[xy[i].y] = true;
	    for (int i=0; i<n; ++i)
		if (v_aux[i]) v[nv++]=i;
	    if (nv<2)
		best=0;
	    /*
	    else if(nv==2) 
		best=a[v[0]][v[1]];
	    */
	    else 
		for (int nx=0; nx<=nv-2; ++nx)
		    best = Math.min(best,minSteinerTree(v,nv,nx,0));
	    mStT[subset]=best;
	    //System.err.println(best);
	}
	return mStT[subset];
    }
    
    /* v[0..nv-1] are points that must be included
     * n_extra is how many extra nodes we may use
     * u is the next node to consider 
     */
    int minSteinerTree(int[] v, int nv, int n_extra, int u) {
	if (n_extra==0) return minSpanTree(v,nv);
	if (n-u<n_extra) return INF;
	int best = minSteinerTree(v,nv,n_extra,u+1);
	if (!used[u]) {
	    //System.err.println("  Add " + im.str(u));
	    v[nv]=u;
	    best = Math.min(best,minSteinerTree(v,nv+1,n_extra-1,u+1));
	    // System.err.println("  Drop " + im.str(u));
	}
	return best;
    }

    int minSpanTree(int[] v, int nv)
    {
	if (nv<2) return 0;
	int[] d=new int[nv];
	/*
	for (int i=0; i<nv; ++i) {
	    System.err.print("  " + im.str(v[i]));
	}
	System.err.println();
	*/
	for (int i=0; i<nv; ++i) d[i]=a[v[0]][v[i]];
	int cost=0;
	d[0]=INF;
	//System.err.println("Root " + im.str(v[0]));
	for (int i=0; i<nv-1; ++i) { // nv-1 times
	    int j=0;
	    for (int k=0; k<nv; ++k)
		if (d[j]>d[k]) j=k;
	    //System.err.println("Adding " + im.str(v[j]) + " cost " + d[j]);
	    cost += d[j];
	    d[j]=INF;
	    for (int k=0;k<nv;++k)
		if (d[k] != INF)
		    d[k] = Math.min(d[k],a[v[j]][v[k]]);
	}
	//System.err.println("      min span tree has cost " + cost);
	return cost;
	
    }
}