#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define KMAX 20
#define NMAX 1000
#define SMAX 1 << 16
#define INF 0x3f3f3f3f
#define pb push_back
#define sz size()
#define mp make_pair


struct muchie{unsigned long int x,y,cost,cap;} aux;
struct node{unsigned int x,y,cost;} hp[3*NMAX];

unsigned long int poz[KMAX],n,i,j,k,t,a[KMAX][KMAX][KMAX];
unsigned long int x,y,cost,cap,nx,ny,m,d[NMAX];
unsigned long int uz[NMAX],dimh;
unsigned long int S[SMAX][KMAX];

vector< pair<int,int> > G[NMAX];
vector<muchie> muc;

void extract()
{

hp[1]=hp[dimh];
dimh--;
}

inline long int MINN(long int a, long int b)
{
if (a<b) return a;
return b;
}

void ADD(long int x, long int y, long int cost)
{

long int i;
node aux;
dimh++;
hp[dimh].x=x;
hp[dimh].y=y;
hp[dimh].cost=cost;

i=dimh;

while ( (hp[i/2].cost>hp[i].cost)&&(i>=1) )
        {
        aux=hp[i/2];
        hp[i/2]=hp[i];
        hp[i]=aux;
        i/=2;
        }
}

void recheap(long int nod)
{
long int minim,poz;
node aux;

minim=hp[nod].cost;
poz=nod;

if ( (nod*2<=dimh) && (hp[nod*2].cost < minim ) ) {minim=hp[nod*2].cost;poz=nod*2;}
if ( (nod*2+1<=dimh) && (hp[nod*2+1].cost < minim ) ) {minim=hp[nod*2+1].cost;poz=nod*2+1;}

if (poz!=nod)
        {
        aux=hp[nod];
        hp[nod]=hp[poz];
        hp[poz]=aux;
        recheap(poz);
        }
}


int main()
{
        freopen("gather.in","r",stdin);
        freopen("gather.out","w",stdout);

        scanf("%lu %lu %lu",&k,&n,&m);

        for (i=1;i<=k;i++)
                scanf("%lu",&poz[i]);

        for (i=1;i<=m;i++)
                {
                scanf("%lu %lu %lu %lu",&x,&y,&cost,&cap);
                aux.x=x;
                aux.y=y;
                aux.cost=cost;
                aux.cap=cap;
                muc.pb(aux);
                }

        for (cap=1;cap<=k;cap++)
                {
                for (j=1;j<=n;j++)
                        vector< pair<int,int> > ().swap(G[j]);

                for (i=0;i<m;i++)
                        {
                        if (muc[i].cap>=cap) {
                                         x=muc[i].x;
                                         y=muc[i].y;
                                         G[x].pb( mp(y,muc[i].cost) );
                                         G[y].pb( mp(x,muc[i].cost) );
                                         }
                        }

                for (i=1;i<=k+1;i++)
                        {
                        for (j=1;j<=n;j++)
                                d[j]=INF;
                        dimh=0;
                        nx=1;
                        if (i<k+1) nx=poz[i];

                        d[nx]=0;
                        for (j=0;j<G[nx].sz;j++)
                                ADD(nx,G[nx][j].first,G[nx][j].second);

                        for (j=1;j<n;j++)
                                {
                                while (d[ hp[1].y ] != INF) {extract();recheap(1);}

                                d[ hp[1].y ] = hp[1].cost;
                                x=hp[1].y;

                                extract();
                                recheap(1);

                                
                                for (t=0;t<G[x].sz;t++)
                                        if (d[ G[x][t].first ] == INF) ADD(x,G[x][t].first, d[x] + G[x][t].second);

                                }
                                
                        for (j=1;j<=k+1;j++)
                                {
                                ny=1;
                                if (j<k+1) ny=poz[j];
                                a[cap][i][j]=d[ny];
                                }                                
                        }

                }
                
        for (i=1;i<=k;i++,printf("\n\n") )
                for (j=1;j<=k+1;j++,printf("\n") )
                        for (t=1;t<=k+1;t++)
                                printf("%ld ",a[i][j][t]);
                                
        unsigned long int v[KMAX],nr1,p;

        for (i=1;i<=k+1;i++) S[0][i]=a[1][i][k+1];

        for (i=1;i< (1 << k) ;i++)
                {
                nr1=0;
                memset(v,0,sizeof(v));
                for (x=i,t=1;x;x/=2,t++) {v[t]=x%2;nr1+=x%2;}
                
                for (j=1;j<=k+1;j++)
                        {
                        S[i][j]=INF;
                        for (t=1,p=1;t<=k;p=p*2,t++)
                                {
                                if (!v[t]) continue;
                                S[i][j]=MINN(S[i][j],S[i-p][t] + a[nr1][j][t] * (nr1+1) );
                                }

                        }
                }
        unsigned long int minim;

        minim=INF;
        for (i=1;i<=k;i++)
                if (S[ (1 << k)-1 ][i] < minim) minim = S[ (1<<k) - 1 ][i];
        printf("%lu",minim);
        return 0;
}