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

#define INF ((1 << 30) - 1)

using namespace std;

/*
    dp[i][j][k] = distanta minima de la nodul locatiePrizonieri[i] pana la
                  k, avand j prizonieri

                cu alte cuvinte,

                = distanta minima de la nodul locatiePrizonieri[i] pana la
                  k, mergand doar pe muchiile pe care pot circula cel putin
                  j prizonieri

    dp2[i][j] = distanta minima de la celula 1 catre nodul locatiePrizonieri[i],
                fiind urmariti de prizionierii din masca j
*/

typedef pair<int, int> pii;

const int NMAX = 750,
          KMAX = 15,
          MMAX = 1250;

struct elem {
    int dest, ln, maxPriz;
};

int n, k, m, locatiePrizonieri[KMAX + 1],
    nrPrizonieri[(1 << KMAX) + 1],
    dp[KMAX + 1][KMAX + 1][NMAX + 1],
    dp2[KMAX + 1][(1 << KMAX) + 1];
vector<elem> adj[NMAX + 1];
priority_queue<pii, vector<pii>, greater<pii> > pq, gol;

inline void dij(const int START, const int MAXPRIZ) {
    for(int i = 1; i <= n; ++i)
        dp[START][MAXPRIZ][i] = INF;
    dp[START][MAXPRIZ][locatiePrizonieri[START]] = 0;

    pq = gol;
    pq.push({0, locatiePrizonieri[START]});
    while(!pq.empty()) {
        const int crtLn = pq.top().first,
                  crtNod = pq.top().second;
        pq.pop();

        if(dp[START][MAXPRIZ][crtNod] != crtLn)
            continue;

        for(const auto &el : adj[crtNod]) {
            if(el.maxPriz >= MAXPRIZ) {
                const int newNod = el.dest,
                          newLn = crtLn + el.ln;
                if(newLn < dp[START][MAXPRIZ][newNod])
                    dp[START][MAXPRIZ][newNod] = newLn,
                    pq.push({newLn, newNod});
            }
        }
    }
}

int main()
{
    freopen("gather.in", "r", stdin);
    freopen("gather.out", "w", stdout);
    scanf("%d%d%d", &k, &n, &m);
    for(int i = 0; i <= (1 << k); ++i)
        nrPrizonieri[i] = nrPrizonieri[i / 2] + i % 2;

    for(int i = 1; i <= k; ++i)
        scanf("%d", &locatiePrizonieri[i]);
    for(int x, y, z, t, i = 1; i <= m; ++i)
        scanf("%d%d%d%d", &x, &y, &z, &t),
        adj[x].push_back({y, z, t}),
        adj[y].push_back({x, z, t});

    for(int start = 1; start <= k; ++start)
        for(int maxPriz = 1; maxPriz <= k; ++maxPriz)
            dij(start, maxPriz);
    for(int i = 1; i <= k; ++i)
        for(int j = 0; j <= (1 << k); ++j)
            dp2[i][j] = INF;
    for(int i = 0; i < k; ++i)
        dp2[i + 1][1 << i] = dp[i + 1][1][1];

    for(int mask = 1; mask < (1 << k); ++mask)
        for(int i = 0; i < k; ++i)
            if(mask & (1 << i))
                for(int j = 0; j < k; ++j)
                    if(i != j && (mask & (1 << j)) && dp[i + 1][nrPrizonieri[mask ^ (1 << j)]][locatiePrizonieri[j + 1]] != INF) {
                        dp2[j + 1][mask] = min(dp2[j + 1][mask], dp2[i + 1][mask ^ (1 << j)] + (nrPrizonieri[mask ^ (1 << j)] + 1) * dp[i + 1][nrPrizonieri[mask ^ (1 << j)]][locatiePrizonieri[j + 1]]);
                    }
    int ans = INF;
    for(int i = 1; i <= k; ++i)
        ans = min(ans, dp2[i][(1 << k) - 1]);
    printf("%d", ans);
    return 0;
}