#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream f("gather.in");
ofstream g("gather.out");

const unsigned f_mare = 3e+9;
unsigned n, m, k, i, j;
unsigned det[20];
unsigned minim;
unsigned D[20][20][20];
unsigned sol[(1 << 15) + 15][20];

struct coridor {
    unsigned y, l, d;
};

vector <coridor> ls[755];

void citire() {
    unsigned x, y, l, d;
    unsigned i;
    coridor X;

    f >> k >> n >> m;
    for (i = 0; i < k; i++)
        f >> det[i];

    det[k] = 1;

    for (;m;m--) {
        f >> x >> y >> l >> d;
        X.y = y, X.l = l, X.d = d;
        ls[x].push_back(X);
        X.y = x;
        ls[y].push_back(X);
    }
}

inline unsigned nb1(unsigned k) {
    unsigned nr = 0;
    while (k)
        k &= (k-1), nr++;
    return nr;
}

inline void bf(unsigned f) {
    bool act;
    unsigned i, j, x, y, d, l, m;
    unsigned s = det[f];
    queue <unsigned> coada;
    unsigned mat[755][20];

    for (i = 1; i <= n; i++)
        for (j = 0; j <= k; j++)
            mat[i][j] = f_mare;

    for (i = 0; i <= k; i++)
        mat[s][i] = 0;

    coada.push(s);
    while (!coada.empty()) {
        x = coada.front();
        l = ls[x].size();
        coada.pop();
        for (i = 0; i < l; i++) {
            act = 0;
            y = ls[x][i].y;
            d = ls[x][i].l;
            m = ls[x][i].d;
            //g << y << ' ' << d << " " <<  m << " Sanatate\n";

            for (j = 0; j <= m; j++)
                if (mat[x][j] + d < mat[y][j]) {
                    mat[y][j] = mat[x][j] + d;
                    act = 1;
                }
            if (act)
                coada.push(y);
        }
    }
    //g << det[f] << '\n';
    for (i = 0; i < k; i++) {
        for (j = 0; j <= k; j++) {
            D[f][i][j] = mat[ det[i] ][j];
            //g << mat[det[i]][j] << ' ';
        }
        //g << '\n';
    }
    //g << '\n';
}

void rezolvare() {
    unsigned i, j, c, nb;

    for (i = 1; i < (1 << k); i++)
        for (j = 0; j < k; j++)
            sol[i][j] = f_mare;

    for (i = 0; i < k; i++)
        sol[(1<<i)][i] = D[k][i][0];

    for (i = 1; i < (1 << k); i++) {
        for (j = 0; j < k; j++)
            if (i & (1 << j)){
                nb = nb1(i);
                minim = sol[i][j];
                for (c = 0; c < k; c++)
                    if ((i & (1 << c)) && c != j)
                        minim = min(minim, sol[i ^ (1 << j)][c] + nb*D[c][j][nb-1]);
                sol[i][j] = minim;
            }
    }



    minim = f_mare;
    for (i = 0; i < k; i++)
        minim = min(minim, sol[(1 << k)-1][i]);
}

void afisare() { g << minim; }

int main() {
    citire();

    for (int i = 0; i <= k; i++)
        bf(i);

    rezolvare();
    afisare();
    return 0;
}