#include <bits/stdc++.h>

#define MaxN 755
#define MaxK 16
#define inf  (ll)(1e9)
#define ll   long long

std::ifstream InFile("gather.in");
std::ofstream OutFile("gather.out");

ll ContainedInmate[MaxN],
    InmateCell[MaxK];
ll K;

inline ll BitCount(ll x) {
    if(x==0) return 0;
    return (x&1) + BitCount(x/2);
}

struct DijkstraStruct {
    ll *DPtr;
    ll Node;
};  bool operator < (const DijkstraStruct &D1, const DijkstraStruct &D2) {
        return D1.DPtr[D1.Node] < D2.DPtr[D2.Node];
}

template <ll NNodes>
struct GraphStruct {
    ll N;
    ll Capacity[NNodes][NNodes],
        EdgeLen[NNodes][NNodes];
    struct NodeStruct {
        std::list <ll> ADC;
    }   Node[NNodes];

    inline void AddEdge(ll x, ll y, ll Len, ll D) {
        Node[x].ADC.push_back(y);
        Node[y].ADC.push_back(x);
        EdgeLen[x][y] = EdgeLen[y][x] = Len;
        Capacity[x][y] = Capacity[y][x] = D;
    }

    ll Dist[MaxK][MaxK][NNodes];               // Dist[i][j][k] - distanta min de la nodul cu detinutul j la nodul k, folosing muchii cu capacitate minim i
    std::priority_queue <DijkstraStruct> DijkstraQueue;

    bool InQueue[NNodes];
    void Dijkstra(ll Inmate, ll MinCapacity) {// MinCapacity - cati detinuti ducem
        ll *D = Dist[MinCapacity][Inmate];
        for (ll i=0; i<=NNodes; ++i)
            D[i+1] = inf, InQueue[i+1] = 0;

        D[InmateCell[Inmate]] = 0;
        InQueue[InmateCell[Inmate]] = 1;
        DijkstraQueue.push({0, InmateCell[Inmate]});

        DijkstraStruct Top;
        while(!DijkstraQueue.empty()) {
            Top = DijkstraQueue.top();
            DijkstraQueue.pop();

            InQueue[Top.Node] = 0;
            for (auto Vecin:Node[Top.Node].ADC) {
                if (D[Vecin] > D[Top.Node] + EdgeLen[Top.Node][Vecin] && Capacity[Top.Node][Vecin] >= MinCapacity) {
                    D[Vecin] = D[Top.Node] + EdgeLen[Top.Node][Vecin];

                    if(!InQueue[Vecin])
                        InQueue[Vecin] = 1,
                        DijkstraQueue.push({D, Vecin});
                }
            }
        }

        for (ll i=1; i<N; ++i)
            if(D[i+1] != inf)
                D[i+1] *= MinCapacity+1;
    }

    void BuildInmateGraph() {
        for (ll i=0, j; i<=K; ++i)
            for (j=0; j<=K+1; ++j)
                Dijkstra(i, j);
    }
};  GraphStruct <MaxN> Graph;

ll Dyn[1<<MaxK][MaxK];
void DP() {
    ll Lim = (1<<(K+1));
    for (ll i=0, j; i<Lim; ++i)
        for (j=0; j<=K; ++j)
            Dyn[i][j] = inf;

    Dyn[1][0] = 0;
    for (ll i=2, j, l, NBits; i<Lim; ++i) {
        NBits = BitCount(i)-2;
        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[NBits][l][InmateCell[j]]);
    }
}

void Citire() {
    InFile >> K >> Graph.N;
    ll M; InFile >> M;

    for (ll i=0, x; i<K; ++i)
        InFile >> InmateCell[i+1],
        InmateCell[i+1]--;

    for (ll i=0, x, y, Len, D; i<M; ++i)
        InFile >> x >> y >> Len >> D,
        x--, y--,
        Graph.AddEdge(x, y, Len, D);
}
void Rezolvare() {
    Graph.BuildInmateGraph();
    DP();

    ll Rez = inf;
    for (ll i=0; i<=K; ++i)
        Rez = std::min(Rez, Dyn[(1<<(K+1))-1][i]);
    OutFile << Rez << '\n';
}


int main()
{
    Citire();
    Rezolvare();

    return 0;
}