#include <bits/stdc++.h>
 
std::ifstream InFile("gather.in");
std::ofstream OutFile("gather.out");
 
#define MaxN 755
#define MaxK 17
#define inf  ((long long)(1) << 50)
#define ll   long long
 
int K;
int Inmate[MaxN];
 
int BitCount(int x) {
    int Counter = 0;
    while(x) Counter ++,
        x &= x-1;
    return Counter;
}
 
struct GraphStruct {
    int N;
    struct NodStruct {
        struct EdgeStruct {
            int Node, Len, Capacity;
        };  std::list <EdgeStruct> ADC;
    }   Node[MaxN];
 
    inline void AddEdge(int x, int y, int Len, int D) {
        Node[x].ADC.push_back({y, Len, D});
        Node[y].ADC.push_back({x, Len, D});
    }
 
    ll Dist[MaxK][MaxK][MaxN];
    struct DijkstraStruct {
        int Node;
        ll *DPtr;
        bool operator < (const DijkstraStruct &D) const {
            return DPtr[Node] > DPtr[D.Node];
        }
    };
    bool InQueue[MaxN];
    void Dijkstra(int Source, int NInmates, ll D[]) {
        std::priority_queue <DijkstraStruct> DijkstraQueue;
        for (int i=0; i<N; ++i)
            D[i] = inf, 
            InQueue[i] = 0;
 
        D[Source] = 0;
        InQueue[Source] = 1;
        DijkstraQueue.push({Source, D});
 
        DijkstraStruct Top;
        while(!DijkstraQueue.empty()) {
            Top = DijkstraQueue.top();
            DijkstraQueue.pop();
            
            InQueue[Top.Node] = 0;
            for (auto Edge:Node[Top.Node].ADC) {
                if(Edge.Capacity >= NInmates && D[Edge.Node] > D[Top.Node] + Edge.Len) {
                    D[Edge.Node] = D[Top.Node] + Edge.Len;
                    if (!InQueue[Edge.Node])
                    	DijkstraQueue.push({Edge.Node, D}),
                    	InQueue[Edge.Node] = 1;
                    }
            }
        }
 
        for (int i=0; i<N; ++i)
            if(D[i] < inf) D[i] *= NInmates+1;
    }
 
    void BuildDist() {
        for (int i=0; i<=K; ++i)
            Dijkstra(0, i, Dist[0][i]);
 
        for (int i=1, j; i<=K; ++i)
            for (j=0; j<=K; ++j)
                Dijkstra(Inmate[i], j, Dist[i][j]);
    }
}   Graph;
 
ll Dyn[1 << MaxK][MaxK];
void DP() {
    int Lim = (1<<(K+1));
    for (int i=0, j; i<Lim; ++i)
        for (j=0; j<=K; ++j)
            Dyn[i][j] = inf;
 
    Dyn[1][0] = 0;
    for (int i=2, j, l, NBits; i<Lim; ++i) {
        NBits = __builtin_popcount(i)-1;
        for (j=0; j<=K; ++j)
            if (i&(1<<j))
                for (l=0; l<=K; ++l)
                    Dyn[i][j] = std::min(Dyn[i][j], Dyn[i^(1<<j)][l] + Graph.Dist[l][NBits-1][Inmate[j]]);
    }
}
 
void Citire() {
    int M;
    InFile >> K >> Graph.N >> M;
    for (int i=1; i<=K; ++i)
        InFile >> Inmate[i],
        --Inmate[i];
 
    for (int i=1, x, y, Len, D; i<=M; ++i)
        InFile >> x >> y >> Len >> D,
        Graph.AddEdge(x-1, y-1, Len, D);
}
 
void Rezolvare() {
    Graph.BuildDist();
    DP();
 
    ll Rez = Dyn[(1<<(K+1))-1][0];
    for (int i=1; i<=K; ++i)
        Rez = std::min(Rez, Dyn[(1<<(K+1))-1][i]);
    OutFile << Rez << '\n';
}
 
int main()
{
    Citire();
    Rezolvare();
 
    return 0;
}