#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("gather.in");
ofstream fout("gather.out");

const int MAXK = 16;
const int MAXN = 750;
int d[MAXK], dp[MAXK][1 + MAXK][MAXN], a[MAXK][1 << MAXK], q[1 + MAXN];
vector<tuple<int,int,int>> G[MAXN];
bitset<MAXN> inQ;

void Dijkstra(int s, int low, int D[]) {
  D[s] = 0;
  int st = 1, dr = 0;
  q[++dr] = s;
  inQ[s] = true;
  while (st <= dr) {
    int u = q[st++];
    inQ[u] = false;
    for (auto it : G[u]) {
      int v, w, c;
      tie(v, w, c) = it;
      if (c >= low && D[v] > D[u] + w) {
        D[v] = D[u] + w;
        if (!inQ[v]) {
          q[++dr] = v;
          inQ[v] = true;
        }
      }
    }
  }
}

void min_self(int &x, int y) {
  if (x > y)
    x = y;
}

int main() {
  int k, n, m;
  fin >> k >> n >> m;
  ++k;
  for (int i = 1; i < k; ++i) {
    fin >> d[i];
    --d[i];
  }
  for (int i = 0; i < m; ++i) {
    int u, v, w, c;
    fin >> u >> v >> w >> c;
    --u, --v;
    G[u].emplace_back(v, w, c);
    G[v].emplace_back(u, w, c);
  }
  memset(dp, INF, sizeof dp);
  for (int i = 0; i < k; ++i)
    for (int j = 0; j <= k; ++j)
      Dijkstra(d[i], j, dp[i][j]);
  memset(a, INF, sizeof a);
  a[0][1] = 0;
  for (int mask = 2; mask < (1 << k); ++mask) {
    int cnt_det = __builtin_popcount(mask) - 1;
    for (int i = 0; i < k; ++i)
      if (mask & (1 << i)) {
        int prev_mask = mask ^ (1 << i);
        for (int j = 0; j < k; ++j) {
          if (a[j][prev_mask] == INF || dp[j][cnt_det - 1][d[i]] == INF)
            continue;
          min_self(a[i][mask], a[j][prev_mask] + cnt_det * dp[j][cnt_det - 1][d[i]]);
        }
      }
  }
  int ans = INF;
  for (int i = 0; i < k; ++i)
    min_self(ans, a[i][(1 << k) - 1]);
  fout << ans << '\n';
  fin.close();
  fout.close();
  return 0;
}