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

using namespace std;

#define KMAX 15
#define NMAX 760
#define INFI 0x3f3f3f3f

#define pb push_back
#define sz size()
#define MP make_pair
#define ff first
#define ss second

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

int a[KMAX][1<<KMAX];
int n, m, k;
vector< pair< int, pair<int, int> > > vec[NMAX];
vector<int> det[NMAX];
short uz[NMAX];
int cel[NMAX], h = 0;
int conf[NMAX];
int nrbit[(1<<KMAX) + 1000];

void read()
{
	scanf("%d %d %d", &k, &n, &m);
	for(int i = 0, x; i < k; ++i)
	{
		scanf("%d", &x);
		if(!uz[x])
			cel[++h] = x;
		++uz[x];
		det[x].pb(i);
	}
	for(int i = 1, x, y, c, d; i <= m; ++i)
	{
		scanf("%d %d %d %d", &x, &y, &c, &d);
		vec[x].pb( MP(y, MP(c, d) ) );
		vec[y].pb( MP(x, MP(c, d) ) );
	}
}	

int drum(int x, int y, int nr)
{
	int _min[NMAX];
	queue<int> q;
	int i, dist;
	memset(_min, INFI, sizeof(_min));
	_min[x] = 0;
	q.push(x);
	while(!q.empty())
	{
		x = q.front(), q.pop();
		for(vector< pair< int, pair<int, int> > > :: iterator it = vec[x].begin(); it != vec[x].end(); ++it)
		{
			if(_min[x] + (*it).ss.ff < _min[(*it).ff] && nr <= (*it).ss.ss)
				_min[(*it).ff] = _min[x] + (*it).ss.ff, q.push((*it).ff);
		}
	}
	return (nr+1)*_min[y];
}


void solve()
{
	memset(a, INFI, sizeof(a));
	queue< pair<int, int> > q;
	int i, j;
	for(i = 1; i <= h; ++i)
	{
		int crt = 0;
		for(crt = 0, j = det[cel[i]].sz-1; j >= 0; --j)
			crt |= (1<<det[cel[i]][j]);
		a[i][crt] = drum(1, cel[i], 0);
		q.push( MP(i, crt) );
		conf[i] = crt;
		//printf("%d %d %d\n", i, cel[i], crt);
	}
	pair<int, int> crt;
	int aux;
	while(!q.empty())
	{
		crt = q.front(), q.pop();
		for(i = 1; i <= h; ++i)
			if((crt.ss & conf[i]) == 0)
			{
                aux = drum(cel[crt.ff], cel[i], nrbit[crt.ss]);
               	if(a[crt.ff][crt.ss] + aux < a[i][crt.ss | conf[i]])
				{
                    //printf("%d  %d  %d\n", cel[crt.ff], aux, cel[i]);
					a[i][crt.ss | conf[i]] = a[crt.ff][crt.ss] + aux;
					q.push( MP(i, (crt.ss | conf[i])) );
				}
            }
        //printf("%d %d %d\n", cel[crt.ff], crt.ss, a[crt.ff][crt.ss]);
	}
}

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

	read();

	for(int i = 1; i < (1<<KMAX); ++i)
		nrbit[i] = nrbit[i>>1] + (i&1);//, printf("%d %d\n", i, nrbit[i]); return 0;

	solve();

	int _min = 2*INFI;
	for(int i = 1; i <= k; ++i)
		_min = MIN(_min, a[i][(1<<k)-1]);
	printf("%d\n", _min);
	
    /*printf("%d\n", drum(3, 2, 1));

	for(int i = 1; i <= k; ++i)
		for(int j = 1; j < (1<<KMAX); ++j)
			if(a[i][j] < INFI)
				printf("%d %d %d\n", cel[i], j, a[i][j]);
    */
	return 0;
}