#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
ifstream si("gather.in");
ofstream so("gather.out");
const int inf=0x3f3f3f3f;
const int maxN=755;
const int maxK=16;
long long v[maxN], w[maxN];
long long d[maxK][maxN][maxK];
long long config, nb1;
long long dp[1<<maxK][maxK];
struct pq {
    long long x, c;
    bool operator<(const pq&e) const {
        return c>e.c;
    }
}el;
priority_queue<pq> H;
struct edge {
    long long x, y, c, d;
}e;
vector<edge> V[maxN];
int bitc(int x) {
    int n1=0;
    while(x) {
        ++n1;
        x&=x-1;
    }
    return n1;
}
int main()
{
    int k, n, m;
    si>>k>>n>>m;
    for(int i=1; i<=k; ++i) {
        int x;
        si>>x;
        --x;
        v[x]=i;
        w[i]=x;
    }
    ++k;
    w[0]=0;
    while(m--) {
        si>>e.x>>e.y>>e.c>>e.d;
        --e.x;
        --e.y;
        V[e.x].push_back(e);
        swap(e.x, e.y);
        V[e.x].push_back(e);
    }
    int node;
    int sol=inf;
    for(int i=0; i<k; ++i) {
        for(int j=0; j<k; ++j) {
            el.x=w[i];
            el.c=0;
            H.push(el);
            for(int x=0; x<n; ++x)
                d[i][x][j]=inf;
            d[i][w[i]][j]=0;
            while(!H.empty()) {
                el=H.top();
                int x=el.x;
                H.pop();
                for(int p=0; p<V[x].size(); ++p) {
                    if(V[x][p].d>=j) {
                        node=V[x][p].y;
                        if(d[i][node][j]>d[i][x][j]+V[x][p].c) {
                            d[i][node][j]=d[i][x][j]+V[x][p].c;
                            el.x=node;
                            el.c=d[i][node][j];
                            H.push(el);
                        }
                    }
                }
            }
        }
    }
    memset(dp, inf, sizeof(dp));
    dp[1][0]=0;
    for(int config=1; config<(1<<k); ++config) {
        int nb1=bitc(config);
        for(int i=0; i<k; ++i) {
            if(config&(1<<i)) {
                for(int j=0; j<k; ++j) {
                    if((config&(1<<j))&&d[j][w[i]][nb1-2]!=inf) {
                        dp[config][i]=min(dp[config][i], dp[config^(1<<i)][j]+(nb1-1)*d[j][w[i]][nb1-2]);
                    }
                }
            }
        }
    }
    for(int i=0; i<k; ++i)
        if(dp[(1<<k)-1][i]<sol) {
            sol=dp[(1<<k)-1][i];
        }
    so<<sol<<'\n';
    return 0;
}