#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 755
#define TMAX (1<<10)

int K, N, M, V[NMAX], T[2*TMAX], X[NMAX];
vector<int> A[NMAX], Ct[NMAX], Cp[NMAX];
long long DP[NMAX][16][16], Dist[NMAX][16], D[NMAX], Sol, INF;

void read()
{
        int i, j, k, ct, cp;

        freopen("gather.in", "r", stdin);
        scanf("%d%d%d", &K, &N, &M);
        for (i = 1; i <= K; i++) scanf("%d", V+i);

        for (k = 0; k < N; k++)
        {
                scanf("%d%d%d%d", &i, &j, &ct, &cp);
                A[i].push_back(j); A[j].push_back(i);
                Ct[i].push_back(ct); Ct[j].push_back(ct);
                Cp[i].push_back(cp); Cp[j].push_back(cp);
        }
}

void update(int x)
{
        int nod = TMAX+x, m;

        T[nod] = x;

        while (nod>1)
        {
                nod  = nod>>1;
                m = nod<<1;
                T[nod] = T[m];
                if (D[ T[m] ]>D[ T[m+1] ]) T[nod] = T[m+1];
        }
}

void dijkstra(int s)
{
        int i, j, k, n, nod;

        for (i = 0; i < NMAX; i++)
            for (j = 0; j < 16; j++) Dist[i][j] = INF;

        for (j = 0; j <= 15; j++)
        {
                for (i = 0; i < NMAX; i++) D[i] = INF-1;

                memset(T,0,sizeof(T));

                D[s] = 0;
                update(s);

                for (i = 0; i < N; i++)
                {
                        nod = T[1]; n = A[nod].size();
                        for (k = 0; k < n; k++)
                            if ( (D[ A[nod][k] ]<INF)&&(Cp[nod][k]>=j)&&( D[A[nod][k]]>(Ct[nod][k]+D[nod]) ) )
                            {
                                D[ A[nod][k] ] = D[nod]+Ct[nod][k];
                                update(A[nod][k]);
                            }
                        Dist[nod][j] = D[nod];
                        D[nod] = INF;
                        update(nod);
                }
        }
        for (i = 1; i <= K; i++)
            for (j = 0; j < 16; j++)
                DP[s][i][j] = Dist[V[i]][j];
}

void perm(int nv, long long sum)
{
        int i, j, ev, ant;

        if (nv==K+1)
        {
                if (Sol>sum)
                   Sol = sum;
                return;
        }

        for (i = 1; i <= K; i++)
        {
                for (j = ev = 1; ev && j < nv; j++)
                    if (X[j]==i) ev = 0;
                if (ev)
                {
                        ant = V[ X[nv-1] ];
                        if ((sum+nv*DP[ant][i][nv-1])<Sol)
                        {
                                X[nv] = i;
                                perm(nv+1, sum+nv*DP[ant][i][nv-1]);
                        }
                }
        }
}

void solve()
{
        int i;
        long long a = 2000000000, b = 2000000000;

        INF = a*b;
        V[0] = 1;
        for (i = 0; i <= K; i++) dijkstra(V[i]);
        Sol = INF;
        perm(1,0);
}

void write()
{
        freopen("gather.out", "w", stdout);
        printf("%lld\n", Sol);
}

int main()
{
        read();
        solve();
        write();
        return 0;
}