#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
long long det[20],k,m,n,d[20][20][20];
struct num{
long long y,l,lim;
};
vector<num>v[1505];
void calc(long long nr){
long long s=det[nr],i,j,nod,sz,mod,y,l,lim;
queue<long long>q;
long long mat[755][20];
for(i=1;i<=n;i++)
for(j=0;j<=k;j++)
mat[i][j]=2000000000000;
for(i=0;i<=k;i++)
mat[s][i]=0;
q.push(s);
while(!q.empty()){
nod=q.front();
q.pop();
sz=v[nod].size();
for(i=0;i<sz;i++){
mod=0;
y=v[nod][i].y;
l=v[nod][i].l;
lim=v[nod][i].lim;
for(j=0;j<=lim;j++)
if (mat[nod][j]+l<mat[y][j]){
mat[y][j]=mat[nod][j]+l;
mod=1;}
if (mod)
q.push(y);}}
for(i=0;i<k;i++)
for(j=0;j<=k;j++)
d[nr][i][j]=mat[det[i]][j];}
long long nb(long long a){
long long nr=0;
while(a){
nr++;
a=a&(a-1);}
return nr;}
long long sol[1<<15][20];
long long solve(){
long long i,j,minim,nrb,c;
for(i=0;i<(1<<k);i++)
for(j=0;j<k;j++)
sol[i][j]=2000000000000;
for(i=0;i<k;i++)
sol[1<<i][i]=d[k][i][0];
for(i=1;i<(1<<k);i++)
for(j=0;j<k;j++)
if (i&(1<<j)){
minim=sol[i][j];
nrb=nb(i);
for(c=0;c<k;c++)
if (i&(1<<c) && c!=j)
minim=min(minim,sol[i^(1<<j)][c]+nrb*d[c][j][nrb-1]);
sol[i][j]=minim;}
minim=2000000000000;
for(i=0;i<k;i++)
minim=min(minim,sol[(1<<k)-1][i]);
return minim;}
int main(){
freopen("gather.in","r",stdin);
freopen("gather.out","w",stdout);
long long i,x,y,l,lim;
num a;
scanf("%lld%lld%lld",&k,&n,&m);
for(i=0;i<k;i++)
scanf("%lld",&det[i]);
for(i=1;i<=m;i++){
scanf("%lld%lld%lld%lld",&x,&y,&l,&lim);
a.y=y;
a.l=l;
a.lim=lim;
v[x].push_back(a);
a.y=x;
v[y].push_back(a);}
det[k]=1;
for(i=0;i<=k;i++)
calc(i);
printf("%lld",solve());
return 0;}