#include <bits/stdc++.h>
using namespace std;

using P = pair<int, int>;

//Graph[i][j][k] ==> i 番目のアルファベットが置かれている
//辺のうち、j から出ている k 番目の辺がつなぐ j 以外の頂点

vector<int> Graph[26][1000];

int main()
{
    int N, M;
    cin >> N >> M;
    //作れるどんな回文の大きさよりも大きい数（今回はどんなに長くても N * N * 2 とかだねたぶん）
    int inf = 1 << 30;
    //真ん中に一文字入れたら回文ができるところで使う
    vector<P> edges;
    //辺の情報を入力
    for (int i = 0; i < M; i++)
    {
        int u, v;
        char c;
        cin >> u >> v >> c;
        u--;
        v--;
        int type = c - 'a';
        Graph[type][v].push_back(u);
        Graph[type][u].push_back(v);
        edges.push_back(P(u, v));
        edges.push_back(P(v, u));
    }
    //ここまでで作る回文の最短の長さをいれる配列
    vector<vector<int>> LEN_up_to_here(N, vector<int>(N, inf));
    LEN_up_to_here[0][N - 1] = 0;
    //この queue に次に見ていく始点と終点の組を入れる
    queue<P> que;
    que.push(P(0, N - 1));
    //次に見る始点と終点の組がなくなるまで
    //始点終点両方から幅優先探索をするイメージ
    //（既にみたものは書き換える必要がないね）
    while (!que.empty())
    {
        //queue の先頭を見る
        P now = que.front();
        que.pop();
        auto [start, goal] = now;
        for (int i = 0; i < 26; i++)
        {
            //start と goal からそのアルファベットの辺が生えているときを考える
            if (Graph[i][start].size() == 0 || Graph[i][goal].size() == 0)
            {
                continue;
            }
            for (auto to0 : Graph[i][start])
            {
                for (auto to1 : Graph[i][goal])
                {
                    if (LEN_up_to_here[to0][to1] != inf)
                    {
                        continue;
                    }
                    //回文の長さは 2 づつ増えるよね（両端から作っていくので）
                    LEN_up_to_here[to0][to1] = LEN_up_to_here[start][goal] + 2;
                    que.push(P(to0, to1));
                }
            }
        }
    }
    int ans = inf;
    //回文ができたよ～～うれしいね
    for (int i = 0; i < N; i++)
    {
        ans = min(ans, LEN_up_to_here[i][i]);
    }
    //あと一文字真ん中に入れたら回文になるよ～～
    for (int i = 0; i < 2 * M; i++)
    {
        auto [start, goal] = edges[i];
        ans = min(ans, LEN_up_to_here[start][goal] + 1);
    }
    // ans==inf となっている時は構築できない時と同値だよね～～（作れるときは inf 未満になるようにしたので）
    if (ans != inf)
    {
        cout << ans << endl;
        return 0;
    }
    cout << -1 << endl;
}
//計算量は幅優先探索以外は平気そう
//幅優先探索での計算量は実質的に
//頂点数 N*N, 辺 M*M とみなせるから、
//O(N*N+M*M)になる...タブンネ
//#pragma GCC optimize ("O2")
//#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int N, M, K;
int to[200001], ne[200001], he[100001];
int D[100001], C[20], Q[100001], q;
int DD[20][20];
int dp[1 << 17][17];

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	N = getint();
	M = getint() * 2;
	rep1(i, M) {
		int a = getint(), b = getint();
		to[i] = b;
		ne[i] = he[a];
		he[a] = i++;
		to[i] = a;
		ne[i] = he[b];
		he[b] = i;
	}
	K = getint();
	rep(i, K) C[i] = getint();

	if (K == 1) {
		printf("1");
		return 0;
	}
	
	const int dekai = 1e8, choidekai = 5e6;
	for (int p = 1; p < K; p++) D[C[p]] = dekai + p;

	rep(k, K - 1) {

		int b = -choidekai * k;
		D[C[k]] = b - choidekai;

		int mada = 0;
		for (int i = K - 1; i > k; i--) mada |= (1 << i);
		int p = 0;
		q = 0;
		Q[q++] = C[k];
		while (mada && p < q) {
			int i = Q[p++];
			int d = D[i] + 1;
			for (int t = he[i]; t; t = ne[t]) {
				int T = to[t];
				if (D[T] >= b) {
					if (D[T] >= dekai) mada ^= 1 << (D[T] - dekai);
					D[T] = d;
					Q[q++] = T;
				}
			}
		}
		rep(p, K) {
			if (p > k) {
				DD[k][p] = D[C[p]] - b + choidekai;
				DD[p][k] = D[C[p]] - b + choidekai;
			}
			if (p > k + 1) D[C[p]] = dekai + p;
		}
	}
	rep(i, K) dp[1 << i][i] = 1 - choidekai;


	rep1(b, (1 << K) - 1) {
		int X[17], Y[17];
		auto x = X, y = Y;
		rep(i, K) {
			if (b >> i & 1) *x++ = i;
			else *y++ = i;
		}
		auto dp0 = dp[b];
		for (auto j = Y; j < y; j++) {
			int saishou = 0;
			for (auto i = X; i < x; i++) {
				if (saishou > dp0[*i] + DD[*j][*i]) saishou = dp0[*i] + DD[*j][*i];
			}
			dp[1 << *j | b][*j] = saishou;
		}
	}

	int kotae = 0;
	rep(i, K) chmin(kotae, dp[(1 << K) - 1][i]);

	if (kotae < 0) printf("%d", kotae + choidekai);
	else printf("-1");

	Would you please return 0;
}