#include <cstdio>
#include <cstring>
#include <utility>
#include <list>
using namespace std;

#define f first
#define s second
#define ul unsigned long

const ul MAX_K = 8;
const ul MAX_N = 760;
const ul MAX_M = 1260;

inline ul min(ul a, ul b) { return (a<b)?a:b; }
inline ul nr_biti(ul a) { for (ul nr=0; true; a>>=1) { if ( a==0 ) return nr; nr += (a&1); } }


struct nod {
	ul x, mask;
};

template <typename tip, typename store> 
struct muchie {
	tip x,y;
	store inf;
};

ul K,N,M;
ul start[MAX_K];
list< muchie<ul, pair<ul, ul> > > A;	// first = lungimea, second = capacitatea;
list< muchie<nod, ul> > B;
ul C[MAX_K][1<<MAX_K];

ul D[MAX_K][MAX_N];


void bellman(ul x, ul m) {		// imi pune costul minim din x in i prin muchii de capac >= m
	memset(D[m],0x3f, sizeof(D[m]));
	D[m][x] = 0;

	for (ul count=0; true /*count<N-1*/; ++count) {
		bool merge=false;
		list< muchie< ul, pair<ul,ul> > >::iterator it;

		for (it=A.begin(); it!=A.end(); ++it) {
			muchie<ul, pair<ul,ul> > tmp = *it;
			if ( tmp.inf.s >= m ) {
				ul st = tmp.x, dr = tmp.y, v = tmp.inf.f;
				if ( D[m][dr] > D[m][st]+v )
					D[m][dr] = D[m][st]+v, merge = true;
				if ( D[m][st] > D[m][dr]+v )
					D[m][st] = D[m][dr]+v, merge = true;
			}
		}

		if ( !merge ) 
			break;
	}
}


int main() {
	ul i,j;

	freopen("gather.in", "r", stdin);
	scanf("%ld %ld %ld", &K, &N, &M);
	for (i=0; i<K; ++i) scanf("%ld", start+i);
	for (i=0; i<M; ++i) {
		muchie< ul, pair<ul,ul> > tmp;
		scanf("%ld %ld %ld %ld", &tmp.x, &tmp.y, &tmp.inf.f, &tmp.inf.s);
		A.push_back(tmp);
	}
	fclose(stdin);

	for (j=0; j<=K; ++j)
		bellman(1,j);

	for (ul ms=0; ms<(unsigned)(1<<K)-1; ++ms) {
		ul nm = nr_biti(ms);
		for (j=0; j<K; ++j) {
			if ( (ms & (1<<j)) == 0 ) {
				if ( D[nm][start[j]] >= 0x3f3f3f3f )
					continue;
				muchie<nod, ul> tmp;
				tmp.x.x=0, tmp.x.mask=ms;
				tmp.y.x=j, tmp.y.mask=ms+(1<<j);
				tmp.inf = D[nm][start[j]];

				B.push_back(tmp);
			}
		}
	}



	for (i=0; i<K; ++i) {
		if ( start[i]==1 ) continue;	// pe 1 il prelucram separat.

		for (j=1; j<=K; ++j) {
			bellman(start[i],j);
		}

		for (ul ms=1; ms<(unsigned)(1<<K)-1; ++ms) {
			ul nm = nr_biti(ms);
			for (j=0; j<K; ++j) {
				if ( (ms & (1<<j)) == 0 ) {
					if ( D[nm][start[j]] >= 0x3f3f3f3f || i==j )
						continue;
					muchie<nod, ul> tmp;
					tmp.x.x=i, tmp.x.mask=ms;
					tmp.y.x=j, tmp.y.mask=ms+(1<<j);
					if ( ms==0 )
						tmp.inf = D[1][start[j]];
					else
						tmp.inf = D[nm][start[j]];

					B.push_back(tmp);
				}
			}
		}
	}
	
	// Totul OK pana aici
/*	for (list< muchie<nod, ul> >::iterator it=B.begin(); 	it!=B.end(); ++it) {
		muchie<nod, ul> tmp = *it;
		printf("(%ld,%ld) -> (%ld,%ld) = %ld\n", tmp.x.x, tmp.x.mask, tmp.y.x, tmp.y.mask, tmp.inf);
	}
*/

	memset(C, 0x3f, sizeof(C));
	C[0][0] = 0;

	list< muchie<nod,ul> >::iterator it;
	for (ul count=0; true; count++) {
		bool merge = false;
		for (it=B.begin(); it!=B.end(); ++it) {
			muchie<nod, ul> tmp = *it;
			ul nr = nr_biti(tmp.x.mask)+1;
			if ( C[tmp.y.x][tmp.y.mask] > C[tmp.x.x][tmp.x.mask]+tmp.inf*nr ) {
				C[tmp.y.x][tmp.y.mask] = C[tmp.x.x][tmp.x.mask]+tmp.inf*nr, merge=true;
//				printf("Upgrade C[%ld][%ld] = %ld, from (%ld,%ld)\n", tmp.y.x, tmp.y.mask, C[tmp.y.x][tmp.y.mask], tmp.x.x, tmp.x.mask);
			}
		}

		if ( !merge ) break;
	}


	ul raspuns=0x3f3f3f3f;
	for (i=0; i<K; ++i)
		raspuns = min(raspuns, C[i][(1<<K)-1]);

	fprintf(fopen("gather.out","w"), "%lu\n", raspuns);
	return 0;
}