#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long
#define inf (1LL<<35)

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

int n,k,m,i,j,nr,x,a,b,y,msk;
ll rez,l;
int id[800],c[20],bt[66000],p[66000];
ll dr[18][18][18],rz[66000][18],dis[800];
struct drum
{	int nd;ll cst;int mx;	};
struct nod
{	int nd;ll cst;
	bool operator<(const nod &alt)const
	{	return cst>alt.cst;	}
};
vector<drum> ad[800];
priority_queue<nod> q;

void dijkstra(int a,int nrx)
{
	int i,nd;
	ll cst;
	for(i=0;i<=n;i++)
		dis[i]=inf;
 
	dis[a]=0;
	q.push({a,0});
	while(!q.empty())
	{
		nd=q.top().nd;
		cst=q.top().cst;
		q.pop();
		
		for(auto j:ad[nd])
		{
			if(j.mx<nrx)	continue;
			if(cst+(nrx+1)*j.cst<dis[j.nd])
			{
				dis[j.nd]=cst+(nrx+1)*j.cst;
				q.push({j.nd,dis[j.nd]});
			}
		}
	}
	for(i=1;i<=n;i++)
		if(dis[i]!=inf)
			dr[id[a]][id[i]][nrx]=dis[i];
}

int main() {
 
	fin>>k>>n>>m;
	c[1]=1;
	id[1]=1;
	k++;
	for(i=2;i<=k;i++)
		fin>>c[i], id[c[i]]=i;
 
	for(;m--;)
	{
		fin>>i>>j>>a>>x;
		ad[i].push_back({j,a,x});
		ad[j].push_back({i,a,x});
	}
 
	for(i=0;i<=k+1;i++)
		for(j=0;j<=k+1;j++)
			for(l=0;l<=k+1;l++)
				dr[i][j][l]=inf;
 
	for(i=1;i<=k;i++)
		for(j=0;j<=k;j++)
			dijkstra(c[i],j);
 
	for(i=1;i<=66000;i*=2)
		p[i]=p[i/2]+1;
 
	for(i=2;i<=k;i++)
		rz[1|(1<<(i-1))][i]=dr[1][i][0], bt[1|(1<<(i-1))]=1;

	l=(1<<k)-1;
	for(msk=3;msk<=l;msk+=2)
	{
		if(((msk-1)&(msk-2))==0)	continue;
		x=msk-1;
		while(x)
		{
			i=p[(x^(x-1))&x];
			rz[msk][i]=inf;
			n=msk-(1<<(i-1));
			y=n-1;
			while(y)
			{
				j=p[(y^(y-1))&y];
				if(rz[n][j]+dr[j][i][bt[n]]<rz[msk][i]&&dr[j][i][bt[n]]!=inf&&dr[j][i][bt[j]]>=0)
				rz[msk][i]=rz[n][j]+dr[j][i][bt[n]];
				y&=y-1;
			}
			bt[msk]++;
			x&=x-1;
		}
	}
	rez=inf;
	for(i=2;i<=k;i++)
		rez=min(rez,rz[l][i]);
 
	fout<<rez<<"\n";
}