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

using namespace std;

#define KMAX 15
#define NMAX 760
#define INFI (1<<32)LL

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

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

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

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) ) );
	}
}

unsigned drum2(int x, int y, int nr)
{
	unsigned _min[NMAX];
	queue<int> q;
	unsigned i, dist;
	for(i = 0; i < NMAX; ++i)
		_min[i] = INFI;
	_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 drum(int x, int nr)
{
	unsigned aux = x;
        x = cel[x];
        unsigned _min[NMAX];
	queue<int> q;
	unsigned int i, dist;
	for(i = 0; i < NMAX; ++i)
		_min[i] = INFI;
	_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);
		}
	}
	for(i = 1; i <= k; ++i)
        cost[aux][i][nr] = (nr+1)*_min[cel[i]];
}


void solve()
{
	queue< pair<int, int> > q;
	int i, j;
	for(i = 0; i < KMAX; ++i)
		for(j = 0; j < (1<<KMAX); ++j)
			a[i][j] = INFI;
	
	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] = drum2(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;
	unsigned int aux;
	while(!q.empty())
	{
		crt = q.front(), q.pop();
		for(i = 1; i <= h; ++i)
			if((crt.ss & conf[i]) == 0)
			{
                aux = cost[crt.ff][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<<k); ++i)
		nrbit[i] = nrbit[i>>1] + (i&1);//, printf("%d %d\n", i, nrbit[i]); return 0;


    	for(int j, i = 1; i <= h; ++i)
        	for(j = 0; j <= k; ++j)
        {
            drum(i, j);
        }

	solve();

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


	return 0;
}