#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    int N, M; cin >> N >> M;
    vector<vector<vector<int>>> G(N, vector<vector<int>>(26));
    vector<vector<bool>> adj(N, vector<bool>(N, false));
    REP(i, 0, M) {
        int a, b; char c; cin >> a >> b >> c; a--; b--; c -= 'a';
        G[a][c].push_back(b);
        G[b][c].push_back(a);
        adj[a][b] = adj[b][a] = true;
    }

    int ans = 1 << 30;
    queue<pair<int, int>> Q;
    Q.push({0, N - 1});
    vector<vector<int>> dist(N, vector<int>(N, -1));
    dist[0][N - 1] = dist[N - 1][0] = 0;

    while (!Q.empty()) {
        auto [u, v] = Q.front(); Q.pop();
        if (ans <= dist[u][v]) break;
        if (u == v) {
            ans = min(ans, 2 * dist[u][v]);
            continue;
        }
        if (adj[u][v]) {
            ans = min(ans, 2 * dist[u][v] + 1);
            continue;
        }
        REP(i, 0, 26) {
            for (auto x : G[u][i]) {
                for (auto y : G[v][i]) {
                    if (dist[x][y] != -1) continue;
                    dist[x][y] = dist[y][x] = dist[u][v] + 1;
                    Q.push({x, y});
                }
            }
        }
    }
    if (ans < (1 << 30)) cout << ans << endl;
    else cout << -1 << endl;

    return 0;
}

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

#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

void chmin(ll& a, ll b) {
  if (a > b) a = b;
}

int main() {
  int N, M;
  cin >> N >> M;
  
  ll H[N];
  rep(i, N) {
    cin >> H[i];
  }
  sort(H, H+N);
 
  vector<ll> left(N/2), right(N/2);
  rep(i, N/2) {
    left[i] = H[2*i+1] - H[2*i];
    right[i] = H[2*(i+1)] - H[2*i+1];
    
  }
  
  vector<ll> left_sum(N/2 + 1, 0), right_sum(N/2+1, 0);
  rep(i, N/2) {
    left_sum[i+1] = left_sum[i] + left[i];
    right_sum[i+1] = right_sum[i] + right[i];
  }
  
  vector<ll> W(M);
  rep(i, M) {
    cin >> W[i];
  }
  
  ll ans = 10000000000000000;
  
  
  rep(i, M) {
    // 先生を初めて超えるindex
    int x = lower_bound(H, H +N, W[i]) - H;
    
    if (x % 2) {
      chmin(ans, left_sum[(x-1)/2] + (W[i]-H[x-1]) 
          + right_sum[(N-1)/2] - right_sum[(x-1)/2]);
    } else {
      chmin(ans, left_sum[x/2] + (H[x]-W[i])
            + right_sum[(N-1)/2] - right_sum[x/2]);
    }
  }
  
  
  cout << ans << endl;
  

}