#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf 1000000000
#define maxN 752
#define maxK 15
using namespace std;
int sol, val, x, n, i, j, p, m, k, v[maxN], w[maxN], dp[maxN][maxK];
int d[maxK][maxN][maxK];
int Dp[1 << maxK][maxN];
struct pq
{
    int x, c;
    bool operator < (const pq & e) const
    {
        return c > e.c;
    }
} el;
priority_queue < pq > H;
struct edge
{
    int x;
    int y;
    int c;
    int d;
} e;
vector < edge > V[maxN];
void read()
{
    freopen("gather.in", "r", stdin);
    scanf("%d %d %d", &k, &n, &m);
    for (i = 0; i < k; ++ i)
        scanf("%d", &x),
              v[x] = i,
                     w[i] = x;
    while (m --)
    {
        scanf("%d %d %d %d", &e.x, &e.y, &e.c, &e.d);
        V[e.x].push_back(e);
        swap(e.x, e.y);
        V[e.x].push_back(e);
    }
}
void solve()
{
    int node;
    sol = inf;

    for (i = 0; i < k; ++ i)
        for (j = 1; j <= k; ++ j)
        {
            el.x = w[i];
            el.c = 0;
            H.push(el);
            for (x = 1; x <= n; ++ x)
                d[i][x][j] = inf;
            d[i][w[i]][j] = 0;
            while (!H.empty())
            {
                el = H.top();
                x = el.x;
                H.pop();

                for (p = 0; p < V[x].size(); ++ p)
                    if (V[x][p].d >= j)
                    {
                        node = V[x][p].y;
                        val = 0;
                        if (node == 1)
                            val = -V[x][p].c;
                        if (d[i][node][j] > d[i][x][j] + (V[x][p].c * (j + 1)) + val)
                        {
                            d[i][node][j] = d[i][x][j] + (V[x][p].c * (j + 1)) + val;
                            el.x = node;
                            el.c = d[i][node][j];
                            H.push(el);
                        }
                    }
            }

        }
    for (i = 1; i < 1 << k; ++ i)
        for (j = 0; j < k; ++ j)
            dp[i][j] = inf;
    for (i = 0; i < k; ++ i)
        dp[1 << i][i] = d[i][1][1];
    for (i = 1; i < 1 << k; ++ i)
    {
        int config = i, nb1 = 0;
        do
        {
            ++ nb1;
        }
        while(config &= (config - 1));

        for (j = 0; j < k; ++ j)
            if (i & (1 << j))
            {
                for (x = 0; x < k; ++ x)
                    if (!(x & (1 << i)))
                        dp[i + 1 << x][x] = min(dp[i][j] + d[j][w[x]][nb1], dp[i + 1 << x][x]);
                if (i == (1 << k) - 1)
                    sol = min(sol, dp[i][j]);
            }
    }
}
void write()
{
    freopen("gather.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}