#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,msk,nr,x,a,b,y,nd,mx,cat,l;
int id[755],c[20],bt[20],p[66000];
ll cst,rez,dr[18][18][18],rz[66000][18],dis[755];
struct drum
{	int nd,cst,mx;	};
struct nod
{	int nd;ll cst;
	bool operator<(const nod &alt)const
	{	return cst>alt.cst;	}
};
vector<drum> ad[755];
priority_queue<nod> q;

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

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;
		
	while(m--)
	{
		fin>>i>>j>>a>>x;
		ad[i].push_back({j,a,x});
		ad[j].push_back({i,a,x});
	}
	
	for(i=1;i<=k;i++)
		for(j=1;j<=k;j++)
			for(l=0;l<k;l++)
				dr[i][j][l]=inf;
	
	dijkstra(1,0);
	for(i=1;i<=k;i++)
		for(j=1;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];
	
	l=(1<<k)-1;
	bt[1]=1;
	for(msk=3;msk<=l;msk+=2)
	{
		if(((msk-1)&(msk-2))==0)	
		{	bt[msk]=1;	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];
				rz[msk][i]=min(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";
}