#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(int 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;
}