#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;

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

int k, n, m, v[20];
struct vrajeala
{
    int x, lg, C;
};
vector <vrajeala> a[755];
int d[20][20][755]; /// dp[i][j][k] = costul minim de a ajunge de la celula prizonierului i cu maxim j prizonieri in celula k
int dp[15][1 << 15];
bitset <755> viz;
priority_queue <pair <int, int> > Q; /// cost, celula
int Dijkstra(int st, int nrp)
{
    int i, cost, x;
    viz.reset();
    Q.push({0, v[st]});
    d[st][nrp][v[st]] = 0;
    while (!Q.empty())
    {
        cost = -Q.top().first;
        x = Q.top().second;
        Q.pop();
        if (viz[x] == 0)
        {
            viz[x] = 1;
            for (vrajeala w : a[x])
            if (w.C <= nrp)
            {
                if (cost + w.lg < d[st][nrp][w.x])
                {
                    d[st][nrp][w.x] = cost + w.lg;
                    Q.push({ -d[st][nrp][w.x], w.x });
                }
            }
        }
    }
}

void Test_Case()
{
    int i, j, x, y, lg, C, q, N, masca, nrp, sol;
    fin >> n >> k >> m;
    for (i = 1; i <= n; i++)
        fin >> v[i];
    sort(v + 1, v + n + 1);

    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> lg >> C;
        a[x].push_back({ y, lg, C });
        a[y].push_back({ x, lg, C });
    }
    
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            for (q = 1; q <= k; q++)
                d[i][j][q] = INF;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            Dijkstra(i, j);

    N = (1 << n);

    for (i = 0; i < n; i++)
        for (masca = 0; masca < N; masca++)
            dp[i][masca] = INF;

    for (i = 0; i < n; i++)
        dp[i][1 << i] = d[i + 1][1][1];

    for (masca = 0; masca < N; masca++)
        for (i = 0; i < n; i++)
            if (masca & (1 << i))
            {
                x = masca - (1 << i);
                nrp = __builtin_popcount(x);
                for (j = 0; j < n; j++)
                    if (x & (1 << j))
                        dp[i][masca] = min(dp[i][masca], dp[j][x] + (nrp + 1) * d[j + 1][nrp][v[i + 1]]);
            }
    sol = INF;
    for (i = 0; i < n; i++)
        sol = min(sol, dp[i][N - 1]);
    fout << sol << "\n";
}

int main()
{
    int t;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    t = 1;
    while (t--)
        Test_Case();

    return 0;
}