#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in ("gather.in");
ofstream out ("gather.out");

int const nmax = 750;
int const kmax = 15;
int const inf = 1000000000;
struct Edge {
  int to;
  int cost;
  int d;
};
vector<Edge> g[5 + nmax];
int w[5 + kmax];
int cost[5 + kmax][5 + kmax][5 + kmax];///fastest way from ith prisoner to the jth one using only tunnels with cap <= h
int k , n , m;
void explore(int node, int cap) {
  int start = node;
  int dp2[5 + nmax];
  for(int i = 1 ; i <= n ; i++) {
    dp2[i] = -1;
  }
  dp2[w[node]] = 0;
  queue<int> q;
  q.push(w[node]);
  while(0 < q.size()){
    node = q.front();
    q.pop();
    for(int h = 0 ; h < g[node].size() ;h++){
      Edge &e = g[node][h];
      int newnode = e.to;
      if(cap <= e.d){
        if(dp2[newnode] == -1 || dp2[node] + e.cost < dp2[newnode]){
          dp2[newnode] = dp2[node] + e.cost;
          q.push(newnode);
        }
      }
    }
  }
  for(int i = 0 ; i <= k ;i++){
    cost[start][i][cap] = dp2[w[i]];
  }
}
int dp[5 + (1 << (kmax + 1))][5 + kmax];
int nrofbit(int x){
  int p = 0;
  while(0 < x){
    x = x & (x - 1);
    p++;
  }
  return p;
}
int main() {
  in>>k>>n>>m;
  w[0] = 1;
  for(int i = 1 ; i <= k ; i++) {
    in >> w[i];
  }
  for(int i = 1 ; i <= m ; i++) {
    int a, b, c,d;
    in >> a >> b >> c >> d;
    g[a].push_back({b,c, d});
    g[b].push_back({a, c, d});
  }
  for(int i = 0 ; i <= k ; i++) {
    for(int j = 0 ; j <= k ; j++) {
      explore(i, j);
    }
  }
  int maxmask = (1 << (k + 1)) - 1;
  for(int j = 0 ; j <= k ;j++){
    for(int i = 0 ; i <= maxmask ;i++){
      dp[i][j] = -1;
    }
  }
  dp[1][0] = 0;
  int smin = inf;
  for(int i = 0 ; i <= maxmask ;i++){
    for(int j = 0 ; j <= k ;j++){
      if(dp[i][j] != -1){

        for(int h = 1 ; h <= k ;h++){
          if(j != h && ((1 << h) & i) == 0 && cost[j][h][nrofbit(i) - 1] != -1){
            int newmask = ((1 << h) | i);
            int newcost = dp[i][j] + cost[j][h][nrofbit(i) - 1] * nrofbit(i);
            if(dp[newmask][h] == -1 || newcost < dp[newmask][h]){
              //cout<<newmask<<" "<<h<<" "<<newcost<<'\n';
              dp[newmask][h] = newcost;
            }
          }
        }
        if(i == maxmask){
          if(dp[i][j] < smin){
            smin = dp[i][j];
          }
        }
      }
    }
  }
  out<<smin;
  return 0;
}