#include <stdio.h>
#include <vector>
#define Kmax 15+2
#define Nmax 750+1
#define x first
#define y second
#define INF 1000000000000LL
#define Pmax (1<<15)+1
#define mp make_pair
#define pb push_back
#define LL long long

using namespace std;

vector< pair< int, pair<int,int> > >v[Nmax];
int D[Kmax],h[Nmax],poz[Nmax],Nr_inc[Nmax];
LL dist[Kmax][Kmax][Kmax], a[Pmax][Kmax],d[Nmax];
LL rez;
int K,N,M,wh,nrd,dh,gigel;

inline LL Minim(LL x,LL y){ return x<y ? x:y; }

inline void swap(int i,int j){
	int aux;
	aux=h[i]; h[i]=h[j]; h[j]=aux;
	poz[h[i]]=i; poz[h[j]]=j;
}
inline void Up(int k){
	while( k/2 && d[h[k/2]] > d[h[k]] ){
		swap(k,k/2);
		k/=2;
	}
}
inline void Down(int k){
	int mn=0;
	while( mn != k ){
		mn=k;
		if(2*mn <= dh && d[h[2*mn]] < d[h[k]] ) k=2*mn;
		if(2*mn+1 <= dh && d[h[2*mn+1]] < d[h[k]] ) k=2*mn+1;
		swap(mn,k);
	}
}

void dijkstra(){
	vector< pair< int, pair<int,int> > >:: iterator it;
	int pmin,i;
	
	for(i=1;i<=N;++i) d[i]=INF,h[i]=poz[i]=i;
	dh=N; 
	d[wh]=0;
	Up(wh);
	
	while( dh ){
		swap(1,dh);
		dh--;
		Down(1);
		pmin=h[dh+1];
		
		for(it=v[pmin].begin(); it!=v[pmin].end(); ++it)
			if( (d[it->x] > d[pmin]+it->y.x) && it->y.y>=nrd ){
				d[it->x] = d[pmin]+it->y.x;
				Up(poz[it->x]);
			}
	}
	wh=Nr_inc[wh];
	for(i=1;i<=N;++i) 
		if( Nr_inc[i] ) dist[wh][Nr_inc[i]][nrd]=d[i]; // dc e inchisoare resp care inc
}	

int main(){
	int i,j,q,nr1,aa,b,c,d;
	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",&D[i]), Nr_inc[D[i]]=i;
	for(i=1;i<=M;++i){
		scanf("%d%d%d%d",&aa,&b,&c,&d);
		v[aa].pb(mp(b,mp(c,d)));
		v[b].pb(mp(aa,mp(c,d)));
	}
	
	for(i=1;i<=K;++i)
		for(j=1;j<=K;++j){
			wh=D[i]; nrd=j;
			dijkstra();
		}
		
	D[K+1]=1; Nr_inc[1]=K+1; //gigel
	K++; 
	for(j=1;j<K;++j){
		wh=1; nrd=j;
		dijkstra();
	}
	--K;
	
	for(j=0; j<K; ++j ){
		a[(1<<j)][j+1]=dist[K+1][j+1][1];
		for(q=1;q<=K;++q) // cu omul j in inchisoarea q
			if(q!=j+1)
				a[(1<<j)][q]=dist[K+1][j+1][1]+dist[j+1][q][1]*2; // ca e si gigel 
	}
	
	for(j=1; j<(1<<K); ++j) // config j
		for(q=1;q<=K;++q ){ // celula q
			nr1=0; 
			for(i=0; (1<<i)<=j; ++i)
				if( j&(1<<i) ) ++nr1;
			if(nr1==1){ q=K+1; continue; }
			a[j][q]=INF;

			for(i=0; (1<<i) <=j; ++i)
				if( j &(1<<i) )
					if( a[j^(1<<i)][i+1]!=INF && dist[i+1][q][nr1]!=INF)
						a[j][q]=Minim(a[j][q],a[j^(1<<i)][i+1] + dist[i+1][q][nr1]*(nr1+1));
		}
	
	rez=INF;
	for(i=1;i<=K;++i)
		rez=Minim(rez,a[(1<<K)-1][i]);
	printf("%lld\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}