#include <fstream>
#include <vector>
#include <queue>
#define int long long
#define inf 1e18
using namespace std;
ifstream cin("gather.in");
ofstream cout("gather.out");
int n,m,n2,x,y,c,d,cost[16][16][16],cap[16][16],dp[(1<<16)][16],dist[751][16],a[16];
bool viz[751][16];
struct muchie{
    int x,cost,cap;
};
vector<muchie>v[751];
struct cmp{
    bool operator()(const muchie& a,const muchie& b){
        return a.cost>b.cost;
    }
};
priority_queue<muchie,vector<muchie>,cmp>q;
void dijkstra(int nod){
    for(int i=1;i<=n2;i++)
        for(int j=0;j<=n;j++){
            dist[i][j]=inf;
            viz[i][j]=0;
        }
    q.push({nod,0,n});
    dist[nod][n]=0;
    while(!q.empty()){
        int nod=q.top().x,c=q.top().cap;
        q.pop();
        if(viz[nod][c])
            continue;
        viz[nod][c]=1;
        for(auto i:v[nod]){
            int newc=min(c,i.cap);
            if(dist[i.x][newc]>dist[nod][c]+i.cost){
                dist[i.x][newc]=dist[nod][c]+i.cost;
                q.push({i.x,dist[i.x][newc],newc});
            }
        }
    }
}
void get_dist(int id){
    dijkstra(a[id]);
    for(int i=0;i<n;i++)
        for(int j=n;j>=0;j--)
            cost[id][i][j]=min(dist[a[i]][j],cost[id][i][min(n,j+1)]);
}
void initializare(){
    dijkstra(1);
    for(int i=0;i<n;i++){
        dp[(1<<i)][i]=inf;
        for(int j=0;j<=n;j++)
            dp[(1<<i)][i]=min(dp[(1<<i)][i],dist[a[i]][j]);
    }
}
signed main()
{
    cin>>n>>n2>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>x>>y>>d>>c;
        c=min(c,n);
        v[x].push_back({y,d,c});
        v[y].push_back({x,d,c});
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<=n;k++)
                cost[i][j][k]=inf;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            dp[i][j]=inf;
    for(int i=0;i<n;i++)
        get_dist(i);
    initializare();
    for(int i=1;i<(1<<n);i++){
        int nr=__builtin_popcount(i);
        for(int j=0;j<n;j++)
            if((i>>j)&1)
                for(int k=0;k<n;k++)
                    if(((i>>k)&1)&&dp[i-(1<<k)][j]!=inf&&cost[j][k][nr-1]!=inf)
                        dp[i][k]=min(dp[i][k],dp[i-(1<<k)][j]+cost[j][k][nr-1]*nr);
    }
    int ans=inf;
    for(int i=0;i<n;i++)
        ans=min(ans,dp[(1<<n)-1][i]);
    cout<<ans;
    return 0;
}
/**
    trebuie sa precalculez costul minim de a ajunge de la o celula a unui detinut la alta pentru fecare numar de detinuti
    apoi aplicam un lant hamiltonian
*/