#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
#include <cassert>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i)=0; (i) <= (n); (i)++)
#define CONTAINS_MAP(m, a) ((m).find((a)) != m.end())
#define CONTAINS_SET(m, a) ((m).find((a)) != m.end())
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; exit(0); }
void Yes() { cout << "Yes" << endl; exit(0); }
void No() { cout << "No" << endl; exit(0); }

int N, M;
int X[101];
vector<int>Y[20];
vector<int>Z[20];

int _dp[1000000];

int bit_count(ull v)
{
	ull count = (v & 0x5555555555555555ULL) + ((v >> 1ULL) & 0x5555555555555555ULL);
	count = (count & 0x3333333333333333ULL) + ((count >> 2ULL) & 0x3333333333333333ULL);
	count = (count & 0x0f0f0f0f0f0f0f0fULL) + ((count >> 4ULL) & 0x0f0f0f0f0f0f0f0fULL);
	count = (count & 0x00ff00ff00ff00ffULL) + ((count >> 8ULL) & 0x00ff00ff00ff00ffULL);
	count = (count & 0x0000ffff0000ffffULL) + ((count >> 16ULL) & 0x0000ffff0000ffffULL);
	return (int)((count & 0x00000000ffffffffULL) + ((count >> 32ULL) & 0x00000000ffffffffULL));
}

signed main()
{
	cin >> N >> M;
	//REP(i, M) cin >> X[i] >> Y[i] >> Z[i];
	REP(i, M)
	{
		int x, y, z;
		cin >> x >> y >> z;

		Y[x].push_back(y);
		Z[x].push_back(z);
	}

	int dp_max = (1LL << N);
	_dp[0] = 1;

	for (int i = 0; i < dp_max; i++)
	{
		int prev = _dp[i];

		for (int j = 0; j < N; j++)
		{
			int cur = (1LL << j);
			if ((i & cur) == 0)
			{
				int bitcnt = bit_count(i | cur);
				if (Y[bitcnt].size() == 0)
				{
					_dp[i | cur] += _dp[i];
				}
				else
				{
					bool is_valid = true;
					for (int k = 0; k < Y[bitcnt].size(); k++)
					{
						int y = Y[bitcnt][k];
						int z = Z[bitcnt][k];
						int mask = (1LL << y) - 1;
						int b = ((i | cur) & mask);
						int cnt = bit_count(b);
						if (cnt > z)
						{
							is_valid = false;
						}
					}
					if (is_valid)
					{
						_dp[i | cur] += _dp[i];
					}
				}
			}
			else
			{
			}
		}
	}

	cout << _dp[(1LL << N) - 1] << endl;
}




// Created at 2021/02/07 22:38
// {TODO}WA, {TODO}min, {TODO}diff
// goal: {TODO}min
#include <bits/stdc++.h>
//#include <atcoder/all>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i, n) for (lint i = 0, i##_len = n; i < i##_len; i++)
#define rep2(i, n) for (lint i = 1, i##_len = n; i <= i##_len; i++)
#define rep3(i, s, e) for (lint i = s, i##_len = e; i < i##_len; i++)
#define all(i) (i).begin(), (i).end()
#define print(s) cout << s << '\n';
#define print2(s1, s2) cout << s1 << ' ' << s2 << '\n';
#define mk_p make_pair
using namespace std;
//using namespace atcoder;
using lint = long long;
using pi = pair<int, int>;
using pl = pair<lint, lint>;
using vi = vector<int>;
using vl = vector<lint>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using qi = queue<int>;
using ql = queue<lint>;
constexpr int INF = 1 << 30;
constexpr lint INFl = 1LL << 62;

template<class T, class U>
istream &operator>>(istream &is, pair<T, U> &pair) {
    is >> pair.first >> pair.second;
    return is;
}

template<class T, class U>
ostream &operator<<(ostream &os, pair <T, U> &pair) {
    os << pair.first << " " << pair.second;
    return os;
}

template<class T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &v : vec) is >> v;
    return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << '[';
    for (auto v : vec) os << v << ',';
    os << ']';
    return os;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout << fixed << setprecision(15);
    /*----------------------------------------------------*/
    int n, m; cin >> n >> m;
    vvi g(n);
    rep(i, m) {
        int ai, bi; cin >> ai >> bi;
        ai--; bi--;
        g.at(ai).push_back(bi);
        g.at(bi).push_back(ai);
    }
    int k; cin >> k;
    vi c(k); cin >> c;
    for (int &ci : c) ci--;

    vvi dist(k, vi(k, INF));

    rep(i, k) {
        int start = c.at(i);
        vi disti(n, INF);
        qi q;
        disti.at(start) = 0;
        q.push(start);
        while (!q.empty()) {
            int now = q.front();
            q.pop();

            for (int next : g.at(now)) {
                if (chmin(disti.at(next), disti.at(now) + 1)) {
                    q.push(next);
                }
            }
        }
        rep(j, k) {
            dist.at(i).at(j) = disti.at(c.at(j));
        }
    }

//    print(g)
//    print(dist)

    vvi dp(1 << k, vi(k, INF));
    rep(start, k) {
        dp.at(1 << start).at(start) = 1;
    }
    rep(went, 1 << k) rep(now, k) {
        rep(next, k) {
            if (dist.at(now).at(next) != INF) {
                chmin(dp.at(went|1 << next).at(next), dp.at(went).at(now) + dist.at(now).at(next));
            }
        }
    }
    int ans = INF;
    rep(last, k) {
        chmin(ans, dp.back().at(last));
    }
    if (ans == INF) print(-1)
    else print(ans)
}
// break? continue?
// 時間? メモリ?
// map->bucket?
// あまり->非負か確認
// set? multiset?
// オーバーフロー確認(最大値を求める)
// 入力確認
// 型確認
// ループ回数確認(TLE)
// 小数の計算は避けよう(割り算)(0割りだめ！絶対！)
// Python を使っては?
// 擬似コードを作っては?
// 汚くてもok
