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

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vec first
#define cost second.first
#define cap second.second
#define sz size()
#define clearV(_x) memset(_x, 0, sizeof(_x) )

const int maxN = 751;
const int maxD = 16;
const int INF = 2000000000;

vector< pair<int, pair<int,int> > > much[ maxN ];
vector< pair<int, pair<int,int> > >::iterator muchIt;

vector< pair< int, int > > stari[2];
vector< pair< int, int > >::iterator stariIt;

int cr;
int distMn[ maxD ][ 32769 ];
bool ap[ maxD ][ 32769 ];
int distC[ maxD ][ maxD ];

int heap[ maxN ];
int pozheap[ maxN ];
int lh;
int distCC[ maxN ];

int N, K, M;
int det[ maxD ];
int tmp = 0;
int distMnT;

void pop( int x );
void push(  int x );

void make_dist( int nods, int capa ) {
	int i,j;
	int nodc;
	lh = 1;

	clearV( heap );
	clearV( pozheap );
	clearV( distCC );

	heap[ 1 ] = det[ nods ];
	pozheap[ det[ nods ] ] = 1;

	for ( i = 1; i <= N; i++ ) {
		if ( i != det[ nods ] ) {
			lh++;
			heap[ lh ] = i;
			pozheap[ i ] = lh;
		}
		distCC[ i ] = INF;
	}
	distCC[ det[ nods ] ] = 0;
	while ( lh ) {
		nodc = heap[ 1 ];
		for ( i = 0; i < much[ nodc ].sz; i++ ) {
				if ( distCC[ much[nodc][i].vec ] > distCC[ nodc ] + much[nodc][i].cost && much[nodc][i].cap >= capa-1 ) {
				distCC[ much[nodc][i].vec ] = distCC[ nodc ] + much[nodc][i].cost;
				pop( pozheap[ much[nodc][i].vec ] );
			}
		}
		heap[ 1 ] = heap[ lh ];
		pozheap[ heap[1] ] = 1;
		lh--;
		push( 1 );

	}
	for( int i = 1; i <= K+1; i++ )
		distC[ nods ][ i ] = distCC[ det[ i ] ] * capa;
}

void pop( int x ) {
	int aux;
	while ( x / 2 && distCC[ heap[x/2] ] > distCC[ heap[x] ] ) {
		aux = heap[x];
		heap[x] = heap[x/2];
		heap[x/2] = aux;

		pozheap[ heap[x] ] = x;
		pozheap[ heap[x/2] ] = x/2;
	}
}

void push( int x ) {
	int q=0,aux;
	while (1) {
		q = x;
		if ( 2*x+1 <= lh && distCC[ heap[ q ] ] > distCC[ heap[ 2*x+1 ] ] )
			q = 2*x+1;
		if ( 2*x <= lh && distCC[ heap[ q ] ] > distCC[ heap[ 2*x ] ] )
			q = 2*x;

		if ( x == q ) break;
		aux = heap[x];
		heap[x] = heap[q];
		heap[q] = aux;

		pozheap[ heap[x] ] = x;
		pozheap[ heap[q] ] = q;
	}
}

int main()
{
	int a,b,c,d;
	freopen("gather.in","r",stdin);
	freopen("gather.out","w",stdout);

	scanf("%d %d %d\n", &K, &N, &M );

	for ( int i = 1; i <= K; i++ )
		scanf("%d", &det[ i ] );
	det[ 0 ] = 1;
	for ( int i = 1; i <= M; i++ ) {
		scanf("%d %d %d %d\n", &a, &b, &c, &d );
		much[ a ].pb( mp( b, mp( c, d ) ) );
		much[ b ].pb( mp( a, mp( c, d ) ) );
	}

	stari[cr].pb( mp( 1, 0 ) );
	ap[ 1 ][ 0 ] = 1;
	while(1) {
		tmp++;
		clearV( distC );
		for( int i = 0; i <= K; i++ )
			make_dist( i, tmp );
		for( int i = 0; i < stari[cr].sz; i++ )
			for( int j = 1; j <= K; j++ ) 
				if ( !( stari[cr][i].ff & ( 1 << j ) ) ) {
					if ( ! ap[ stari[cr][i].ff + (1<<j) ][ j ] ) {
						stari[ 1-cr ].pb( mp( stari[cr][i].ff+(1<<j), j ) );
						distMn[ stari[cr][i].ff+(1<<j) ][ j ] = distMn[ stari[cr][i].ff ][ stari[cr][i].ss ] + distC[ stari[cr][i].ss ][ j ];
						ap[ stari[cr][i].ff+(1<<j) ][ j ] = 1;
					}
					else 
						if ( distMn[ stari[cr][i].ff+(1<<j) ][ j ] > distMn[ stari[cr][i].ff ][ stari[cr][i].ss ] + distC[ stari[cr][i].ss ][ j ] )
							distMn[ stari[cr][i].ff+(1<<j) ][ j ] = distMn[ stari[cr][i].ff ][ stari[cr][i].ss ] + distC[ stari[cr][i].ss ][ j ];
				}
		if ( stari[1-cr].empty() ) break;
		stari[cr].clear();
		cr = 1-cr;
	}
	distMnT = INF;
	for ( int i = 1; i <= K; i++ ) 
		if ( distMn[ (1<<(K+1))-1 ][ i ] < distMnT && ap[ (1<<(K+1))-1 ][ i ] )
			distMnT = distMn[ (1<<(K+1))-1 ][ i ];
	printf("%d\n", distMnT );

	fclose( stdin );
	fclose( stdout );

	return 0;
}