#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 755
#define INF (1LL<<61)

using namespace std;

int N,M,K,det[20],sursa[(1<<15)][15],NOD;
long long dp[(1<<15)][15],a[16][755][17];

struct Edge
{
    int nod,cost;
    long long cap;
};
vector <Edge> L[Nmax];

struct el
{
    int nod;
    long long a,drum;
    bool operator < (const el &A) const
    {
        return a>A.a;
    }
};
priority_queue <el> Q;

inline void Dijkstra()
{
    el w,w1;
    vector <Edge>:: iterator it;
    w.nod=det[NOD]; w.drum=INF; w.a=0;
    Q.push(w);
    while(!Q.empty())
    {
        w=Q.top(); Q.pop();
        for(it=L[w.nod].begin();it!=L[w.nod].end();++it)
        {
            w1.nod=it->nod; w1.drum=min(w.drum,it->cap); w1.a=w.a+it->cost;
            if(a[NOD][w1.nod][w1.drum]>w1.a)
            {
                a[NOD][w1.nod][w1.drum]=w1.a;
                Q.push(w1);
            }
        }
    }
}

inline int nr_biti(int x)
{
    int sol;
    for(sol=0;x;++sol,x=(x&(x-1)));
    return sol;
}

int main()
{
    int M,i,j,k,x,y,z,q,nr;
    long long sol=INF;
    Edge w;
    freopen ("gather.in","r",stdin);
    freopen ("gather.out","w",stdout);
    scanf("%d%d%d", &K,&N,&M);
    for(i=1;i<=K;++i)
        scanf("%d", &det[i]);
    while(M--)
    {
        scanf("%d%d%d%d", &x,&y,&z,&q);
        q=min(q,15);
        w.nod=y; w.cost=z; w.cap=q; L[x].push_back(w);
        w.nod=x; w.cost=z; w.cap=q; L[y].push_back(w);
    }
    for(i=0;i<(1<<K);++i)
        for(j=0;j<K;++j)
            dp[i][j]=INF;
    for(i=0;i<K;++i)
    {
        dp[(1<<i)][i]=0;
        sursa[(1<<i)][i]=i+1;
    }
    for(i=1;i<=K;++i)
        for(j=1;j<=N;++j)
            for(k=0;k<=16;++k)
                a[i][j][k]=INF;
    for(i=1;i<=K;++i)
    {
        NOD=i;
        Dijkstra();
    }
    for(i=1;i<=K;++i)
        for(j=1;j<=N;++j)
            for(k=15;k>=0;--k)
                a[i][j][k]=min(a[i][j][k],a[i][j][k+1]);
    for(i=1;i<(1<<K);++i)
    {
        if((i&(i-1))==0) continue;
        for(j=0;j<K;++j)
            if(((1<<j)&i))
                for(k=0;k<K;++k)
                    if(((1<<k)&i) && k!=j)
                    {
                        nr=nr_biti(i-(1<<j));
                        if(dp[i-(1<<j)][k]==INF || a[k+1][det[j+1]][nr]==INF) continue;
                        if(dp[i][j]>dp[i-(1<<j)][k]+a[k+1][det[j+1]][nr]*(nr+1))
                        {
                            dp[i][j]=dp[i-(1<<j)][k]+a[k+1][det[j+1]][nr]*(nr+1);
                            sursa[i][j]=sursa[i-(1<<j)][k];
                        }
                    }
    }
    for(i=0;i<K;++i)
        sol=min(sol,dp[(1<<K)-1][i]+a[sursa[(1<<K)-1][i]][1][0]);
    printf("%lld\n", sol);
    return 0;
}