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

using namespace std;

ifstream fin ("gather.in"); ofstream fout ("gather.out");

typedef long long i64;

const i64 inf = (1LL << 60);
const int nmax = 750;
const int kmax = 15;
const int stmax = 1 << kmax;

int n, m, k;
int unde[kmax + 1];

bool gata[nmax + 1];

i64 c[kmax + 1][kmax + 1][nmax + 1]; /// costul sa mg cu i de 1, plec din unde[j], aj in k
i64 d[stmax + 1][kmax + 1]; /// am informat st si am aj in unde[j]

struct muchie {
    int x, cap, cost;

    muchie () {}
    muchie (int _x, int _cost, int _cap) {
        x = _x, cost = _cost, cap = _cap;
    }
};
vector< muchie > g[nmax + 1];

struct str {
    int x; i64 cost;

    str () {}
    str (int _x, i64 _cost) {
        x = _x, cost = _cost;
    }

    inline bool operator < (const str &shp) const {
        return (cost > shp.cost);
    }
};
priority_queue< str > h;

void citire () {
    fin >> k >> n >> m;

    for (int i = 0; i < k; ++ i) {
        fin >> unde[ i ];
    }

    for (int i = 1; i <= m; ++ i) {
        int x, y, cost, cap;
        fin >> x >> y >> cost >> cap;

        g[ x ].push_back(muchie(y, cost, cap));
        g[ y ].push_back(muchie(x, cost, cap));
    }
}

void extinde (int cati, int ind, str w) {
    for (auto i : g[ w.x ]) {
        if (i.cap < cati || gata[ i.x ] == 1)
            continue;

        if (c[ cati ][ ind ][ i.x ] > w.cost + 1LL * i.cost * (cati + 1)) {
            c[ cati ][ ind ][ i.x ] = w.cost + 1LL * i.cost * (cati + 1);
            h.push(str(i.x, w.cost + 1LL * i.cost * (cati + 1)));
        }
    }
}

void dijkstra (int cati, int ind, int nst) {
    for (int i = 1; i <= n; ++ i) {
        gata[ i ] = 0;
        c[ cati ][ ind ][ i ] = inf;
    }

    c[ cati ][ ind ][ nst ] = 0;
    h.push(str(nst, 0));

    while (!h.empty()) {
        str x = h.top();
        h.pop();

        if (gata[ x.x ] == 1)
            continue;

        gata[ x.x ] = 1;
        extinde(cati, ind, x);
    }
}

void precalc () {
    dijkstra(0, 0, 1); /// aflu costurile pt Gigel singur cand pleaca din 1

    for (int cnt = 1; cnt <= k; ++ cnt) {
        for (int start = 0; start < k; ++ start) {
            dijkstra(cnt, start, unde[ start ]);
        }
    }
}

int main () {
    citire ();
    precalc ();

    for (int i = 0; i < k; ++ i)
        d[ 0 ][ i ] = inf;

    for (int st = 1; st < (1 << k); ++ st) {
        int nr1 = 0;
        for (int i = 0; i < k; ++ i) {
            nr1 += ((st & (1 << i)) > 0);
        }

        for (int i = 0; i < k; ++ i) {
            if ((st & (1 << i)) == 0)
                continue;

            int stn = st - (1 << i);
            if (stn == 0) {
                d[ st ][ i ] = c[ 0 ][ 0 ][ unde[ i ] ];
            } else {
                d[ st ][ i ] = inf;
            }

            for (int j = 0; j < k; ++ j) {
                if ((stn & (1 << j)) == 0)
                    continue;

                d[ st ][ i ] = min(d[ st ][ i ], d[ stn ][ j ] + c[nr1 - 1][ j ][ unde[ i ] ]);
            }
        }
    }

    int stf = (1 << k) - 1;
    i64 ans = inf;

    for (int i = 0; i < k; ++ i) {
        ans = min(ans, d[ stf ][ i ]);
    }

    fout << ans << "\n";

    fin.close ();
    fout.close ();
    return 0;
}