#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define MAX_N 755
#define MAX_K 16
#define FIN "gather.in"
#define FOUT "gather.out"
#define INF 0x3f3f3f3f
#define f first
#define s second
#define mp make_pair
#define pb push_back

int K, N, M, V[MAX_K], D[MAX_K][MAX_K][MAX_N], A[1<<MAX_K][MAX_K], Res;
vector< pair<int, pair<int, int> > > G[MAX_N];
priority_queue< pair<int, int> > Q;

void dijkstra(int src, int limit, int D[])
{
    int n, d, t;
    vector < pair<int, pair<int, int> > >::iterator it;

    memset(D, 0x3f, N*sizeof(D[0]));
    D[src] = 0;

    for (Q.push(mp(0, src)); !Q.empty(); )
    {
        n = Q.top().s; d = -Q.top().f; Q.pop();
        if (D[n] < d) continue;
        for (it = G[n].begin(); it != G[n].end(); ++it)
        {
            if (it->s.s < limit) continue;
            if (D[it->f] > (t = D[n]+it->s.f))
            {
                D[it->f] = t;
                Q.push(mp(-t, it->f));
            }
        }
    }
}

int main(void)
{
    int i, j, k, a, b, cnt;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d %d", &K, &N, &M);
    for (++K, i = 1; i < K; ++i)
    {
        scanf("%d", &j);
        V[i] = --j;
    }
    for (; M; --M)
    {
        scanf("%d %d %d %d", &i, &j, &a, &b);
        --i, --j;
        G[i].pb(mp(j, mp(a, b)));
        G[j].pb(mp(i, mp(a, b)));
    }

    for (i = 0; i <= K; ++i)
        for (j = 1; j <= K; ++j)
            dijkstra(V[i], j, D[i][j]);

    memset(A, 0x3f, sizeof(A));
    A[1][0] = 0;
    for (i = 2; i < (1<<K); ++i)
    {
        for (cnt = -1, j = i; j; j &= j-1) ++cnt;
        for (j = 0; j < K; ++j)
        {
            if (!(i&(1<<j))) continue;
            for (k = 0; k < K; ++k)
            {
                if (A[i-(1<<j)][k] == INF) continue;
                A[i][j] = min(A[i][j], A[i-(1<<j)][k] + cnt*D[k][cnt][V[j]]);
            }
        }
    }

    Res = A[(1<<K)-1][0];
    for (i = 0; i < K; ++i)
        Res = min(Res, A[(1<<K)-1][i]);
    printf("%d\n", Res);

    return 0;
}