#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int N = 755, P = 16, oo = 2e9;

priority_queue <pair <int, pair <int, int> >, vector <pair <int, pair <int, int> > >, greater <pair <int, pair <int, int> > > > H;
int d[P][N][P], n, m, k, det[N], nr[1 << P], z[P], dp[P][1 << P];
vector <pair <int, pair <int, int> > > g[N];

void dijkstra(int s) {
    d[s][z[s]][k] = 0;
    H.push(make_pair (0, make_pair (z[s], k)));
    while (H.size()) {
        int crt = H.top().first, x = H.top().second.first, y = H.top().second.second;
        H.pop();
        if (crt > d[s][x][y])
            continue;
        for (vector <pair <int, pair <int, int> > > :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (crt + it -> second.first < d[s][it -> first][min(y, it -> second.second)]) {
            d[s][it -> first][min(y, it -> second.second)] = crt + it -> second.first;
            H.push(make_pair (d[s][it -> first][min(y, it -> second.second)], make_pair (it -> first, min(y, it -> second.second))));
        }
    }
    int last = oo;
    for (int i = 0; i < k; ++i) {
        last = oo;
        for (int j = k; j >= 0; --j) {
            if (d[s][z[i]][j] != oo)
                last = min(last, d[s][z[i]][j]);
            d[s][z[i]][j] = min(d[s][z[i]][j], last);
        }
    }
    last = oo;
    for (int j = k; j >= 0; --j) {
        if (d[s][1][j] != oo)
            last = min(last, d[s][1][j]);
        d[s][1][j] = min(d[s][1][j], last);
    }
}

int main() {
    fin >> k >> n >> m;
    for (int i = 0; i < k; ++i)
        fin >> z[i];
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= n; ++j)
            for (int p = 0; p <= k; ++p)
                d[i][j][p] = oo;
    for (int i = 0; i < k; ++i)
        for (int j = 0; j < (1 << k); ++j)
            dp[i][j] = oo;
    for (int x, y, mx, c; m; --m) {
        fin >> x >> y >> c >> mx;
        g[x].push_back(make_pair (y, make_pair(c, mx)));
        g[y].push_back(make_pair (x, make_pair(c, mx)));
    }
    for (int i = 1; i < (1 << k); ++i)
        for (int j = 0; j < k; ++j)
            if (i & (1 << j))
                nr[i]++;
    for (int i = 0; i < k; ++i) {
        dijkstra(i);
        dp[i][0] = d[i][1][0];
    }
    return 0;
    for (int i = 0; i < k; ++i)
        H.push(make_pair (dp[i][0], make_pair(i, 0)));
    while (H.size()) {
        int crt = H.top().first, x = H.top().second.first, dt = H.top().second.second;
        H.pop();
        if (nr[dt] == k) {
            fout << dp[x][dt];
            return 0;
        }
        for (int i = 0; i < k; ++i)
            if (!(dt & (1 << i)) && d[x][z[i]][nr[dt]] != oo && crt + d[x][z[i]][nr[dt]] * (nr[dt] + 1) < dp[i][dt | (1 << i)]) {
                dp[i][dt | (1 << i)] = crt + d[x][z[i]][nr[dt]] * (nr[dt] + 1);
                H.push(make_pair(dp[i][dt | (1 << i)], make_pair(i, (dt | (1 << i)))));
            }
    }
}