#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAXN 750
#define MAXK 15
using namespace std;

int k, n, m;
struct edge {
    int nd, c, d;
};
struct el{
    long long len;
    int node;
    inline bool operator < (const el & other) const {
        return (len > other.len);
    }
};
struct eq{
    long long val;
    int last_inmate, inmates;
};
typedef vector <edge> graf;
graf G[MAXN + 1];
int inmate[MAXK + 1];

long long Dmin[MAXK + 1][MAXK + 1][MAXK + 1];
long long drum[MAXN + 1];
typedef priority_queue <el> Heap;
Heap H;
typedef queue <eq> Queue;
Queue Q;

long long DP[1 << (MAXK + 1)];

inline void reset() {
    for (int i = 1 ; i <= n ; ++i)
        drum[i] = -1;

    while (!H.empty())
        H.pop();
}

inline long long Dijkstra(int a, int b, int nrd) {
    reset();

    drum[a] = 0;
    el x, y;
    x.node = a;
    x.len = 0;
    H.push(x);
    while (drum[b] == -1) {
        x = H.top();
        H.pop();

        drum[x.node] = x.len;

        for (graf :: iterator it = G[x.node].begin() ; it != G[x.node].end() ; ++it) {
            if (nrd <= it -> d && (drum[it -> nd] == -1 || drum[it -> nd] > drum[x.node] + (it -> c * (nrd + 1)))) {
                y.node = it -> nd;
                y.len = drum[x.node] + (it -> c * (nrd + 1));
                H.push(y);
            }
        }
    }

    return drum[b];
}

void precalc() {
    for (int i = 0 ; i < k ; ++i)
        for (int j = i + 1 ; j <= k ; ++j)
            for (int t = 0 ; t < k ; ++t)
                Dmin[i][j][t] = Dmin[j][i][t] = Dijkstra(inmate[i], inmate[j], t);
}

int main () {
    ifstream cin("gather.in");
    ofstream cout("gather.out");

    cin >> k >> n >> m;

    inmate[0] = 1;
    for (int i = 1 ; i <= k ; ++i)
        cin >> inmate[i];

    for (int i = 0 ; i < m ; ++i) {
        int a, b;
        edge e;
        cin >> a >> b >> e.c >> e.d;

        e.nd = b;
        G[a].push_back(e);

        e.nd = a;
        G[b].push_back(e);
    }

    precalc();
    int sz = (1 << (k + 1));
    for (int i = 0 ; i < sz ; ++i)
        DP[i] = -1;

    DP[1 << k] = 0;
    eq x, y;
    x.val = (1 << k);
    x.last_inmate = x.inmates = 0;
    Q.push(x);

    while (!Q.empty()) {
        x = Q.front();
        Q.pop();

        int mask = x.val;

        int cpy_mask = mask;
        for (int i = k ; i > 0 ; --i) {
            if (!(cpy_mask & 1)) {
                int new_mask = mask + (1 << (k - i));
                if (DP[new_mask] == -1 || DP[new_mask] > DP[mask] + Dmin[x.last_inmate][i][x.inmates]) {
                    DP[new_mask] = DP[mask] + Dmin[x.last_inmate][i][x.inmates];
                    y.val = new_mask;
                    y.last_inmate = i;
                    y.inmates = 1 + x.inmates;
                    Q.push(y);
                }
            }

            cpy_mask >>= 1;
        }
    }

    cout << DP[sz - 1] << "\n";

    return 0;

}