#include <vector>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("gather.in");
ofstream fout ("gather.out");

const int Dim = 751,Inf = 0x3f3f3f3f;
pair < int, int > D[1 << 15];
int k, n ,m,P[Dim];
vector < int > V;

bool cmp(int x, int y);

struct TUPLU{
	
	int y,p,c;
};

using VI = vector < TUPLU >;
using VVI = vector < VI >;
VVI G;
priority_queue< pair< int, int > , vector < pair < int, int > > , greater < pair <int, int > > > Q;
int Dijskarta(int x, int y, int cate);
int main() {
	
				fin >> k >> n >> m;
		G = VVI(n + 1);
		for ( int i = 1; i <= k; ++i)
			fin >> P[i];
		int x,y,p,c;
		for (; m > 0; --m) {
		
			fin >> x >> y >> c >> p;
			G[x].push_back({y,p,c});
			G[y].push_back({x,p,c});
		}
		Dijskarta(1,4,1);
		int cost = 0,cate;
		D[0].first = 0, D[0].second = 1;
		V.push_back(0); 
		for ( int mask = 1; mask < (1 << (k)); ++mask) {
			D[mask].first = Inf, D[mask].second = 0;
		V.push_back(mask);
	}
	sort(V.begin(),V.end(),cmp);
		for (const auto & mask : V) {
			cate = 0;
			for ( int q = 0; q < k; ++q)
				if ( (mask & (1 << q) ) )
					++cate;
			for ( int q = 0; q < k; ++q)	
			if ( !(mask & (1 << q)))
			{
				
				 cost = Dijskarta(D[mask].second,P[q+1],cate );
				 if ( D[(mask | ( 1 << q))].first  > D[mask].first + cost ) {
				 D[(mask | ( 1 << q))].first = D[mask].first + cost, D[(mask | (1 << q))].second = P[q+1]; 
				}
			}
				
		} 
		fout << D[(1 << (k)) - 1].first; 
}

bool cmp(int x, int y) {
	
	int xx = 0, yy =  0;
	for ( int i = 1;  i<= k; ++i)
		if ( x & 1 << (i))
			++xx;

	for ( int i = 1;  i <= k; ++i)
		if ( y & 1 << (i))
			++yy;
	return xx < yy;	
}

int Dijskarta(int x, int y, int cate) {
	
	int D[Dim];
	
	for ( int i =  1; i <= n; ++i)
		D[i] = Inf;
	D[x] = 0;
	if ( x == y)
		return 0;
	Q.push({0,x});
	while ( !Q.empty() ) { 
		int dx = Q.top().first;
		int nod = Q.top().second;
		
		Q.pop();
		if ( dx > D[nod] )
			continue;
		for ( const auto & ad : G[nod] )  {
			
			if ( cate<= ad.p and D[ad.y] > dx + ad.c)
		{
			D[ad.y] = dx + ad.c;
			
			Q.push({D[ad.y],ad.y});
		}
	}
	}
		return (cate+1)*D[y];
}