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

using namespace std;

#define nmax 1024
#define mmax 2048
#define kmax 16
#define inf 100011100
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define pt(i) (1<<(i))
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz size()
#define mij ((a+b)>>1)
#define left (i<<1)
#define right ((i<<1)|1)

int MIN(int a,int b) { return a<b?a:b; }

int T[nmax][nmax],ct[kmax][kmax][kmax],S[nmax],X[mmax];
int n,m,k,A[mmax],B[mmax],C[mmax],D[mmax],P[kmax],sol;
int H[kmax][pt(kmax)],pz[nmax];
vector <pair<int,int> > G[nmax];
char viz[nmax];

void init(int i,int a,int b)
{
	if(a==b) X[i]=a;
	if(a>=b) return ;
	init(left,a,mij);
	init(right,mij+1,b);
	X[i]=(S[X[left]]<S[X[right]])?X[left]:X[right];
}

void update(int i,int a,int b,int x)
{
	if(a>=b) return;
	if(x<=mij) 
		update(left,a,mij,x);
	else
		update(right,mij+1,b,x);
	X[i]=(S[X[left]]<S[X[right]])?X[left]:X[right];
}

void calc(int s,int z)
{
	int i,j,ii;
	FOR(i,0,n)
		S[i]=inf*(i!=P[s]);
	init(1,0,n-1);
	FOR(ii,0,n)
	{
		i=X[1];
		if(pz[i]!=-1)
			ct[z][s][pz[i]]=S[i]*(z+1);
		FOR(j,0,G[i].sz)
			if(S[G[i][j].f]!=inf+1 && S[G[i][j].f]>S[i]+G[i][j].s)
				S[G[i][j].f]=S[i]+G[i][j].s, update(1,0,n-1,G[i][j].f);
		S[i]=inf+1;
		update(1,0,n-1,i);
	}
}


int doit(int i,int mask,int z)
{
	int j,aux=inf;
	if(H[i][mask]==-1)
	{	
		FOR(j,0,k)
			if((i!=j)&&(mask&pt(j)))
				aux=MIN(aux,ct[z][i][j]+doit(j,mask^pt(i),z-1));		
		H[i][mask]=aux;
	}
	return H[i][mask];
}

void Add(int i)
{
	G[A[i]].pb(mp(B[i],C[i]));
	G[B[i]].pb(mp(A[i],C[i]));
}

int main()
{
	int i,j;
	freopen("gather.in","r",stdin);
	freopen("gather.out","w",stdout);
	scanf("%d %d %d",&k,&n,&m);
	memset(pz,-1,sizeof(pz));
	FOR(i,0,k)
		scanf("%d",&P[i]),pz[--P[i]]=i;
	FOR(i,0,m)
		scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]),A[i]--,B[i]--;
	FOR(i,0,m)
		if(D[i]>=k)
			Add(i);
	for(j=k-1;j>=0;--j)
	{
		FOR(i,0,m)
			if(D[i]==j)
				Add(i);
		FOR(i,0,k)
			calc(i,j);
	}
	sol=1000111000;
	memset(H,-1,sizeof(H));
	P[k]=0; 
	calc(k,k);	
	FOR(i,0,k)
		H[i][pt(i)]=ct[k][k][i]/(k+1);
	FOR(i,0,k)	
		sol=min(sol,doit(i,pt(k)-1,k-1));
	printf("%d\n",sol);
	return 0;
}