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

using namespace std;

#define KMAX 15
#define NMAX 760

const long long INFI = (1LL << 62);

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

#define intl long long

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

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

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

intl drum2(intl x, intl y, intl nr)
{
	intl _min[NMAX];
	queue<intl> q;
	intl i, dist;
	//memset(_min, INFI, sizeof(_min));
    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< intl, pair<intl, intl> > > :: 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(intl x, intl nr)
{
    intl aux = x;
    x = cel[x];
	intl _min[NMAX];
	queue<intl> q;
	intl i, dist;
//	memset(_min, INFI, sizeof(_min));
    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< intl, pair<intl, intl> > > :: 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()
{
	//memset(a, INFI, sizeof(a));
	queue< pair<intl, intl> > q;
	intl 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)
	{
		intl 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<intl, intl> crt;
	intl 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(intl i = 1; i < (1<<k); ++i)
		nrbit[i] = nrbit[i>>1] + (i&1);//, printf("%d %d\n", i, nrbit[i]); return 0;

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


	solve();

	intl _min = INFI;
	for(intl i = 1; i <= k; ++i)
		_min = MIN(_min, a[i][(1<<k)-1]);
	printf("%lld\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;
}