#include <bits/stdc++.h>

using namespace std;

/// 21:50

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

const int NMAX = 750;
const int KMAX = 15;

int k, n, m;
int detinut[KMAX + 1];
int cnt[1 << (KMAX + 1) + 1];
int dp[KMAX + 1][KMAX + 1][NMAX + 1];
int dist[KMAX + 1][1 << (KMAX + 1) + 1];
/// dp[i][j][q] -> costul minim de a ajunge de pe orasul i pe orasul q folosind doar drumuri cu capatitatea >= j
struct elem
{
    int nod, cost, cnt;
    bool operator < (const elem other) const
    {
        return cost > other.cost;
    }
};

vector<elem> v[NMAX + 5];
priority_queue<elem> coada;

void Dijkstra(int start, int minim)
{
    coada.push({detinut[start], 0, 0});
    dp[start][minim][detinut[start]] = 0;
    while(!coada.empty())
    {
        int nod = coada.top().nod;
        int cost = coada.top().cost;
        coada.pop();
        if(cost != dp[start][minim][nod])
        {
            continue;
        }
        ///fout << nod << ' ' << cost << '\n';
        for(auto it : v[nod])
        {
            if(it.cnt >= minim)
            {
                if(cost + it.cost < dp[start][minim][it.nod])
                {
                    int newcost = cost + it.cost;
                    dp[start][minim][it.nod] = newcost;
                    coada.push({it.nod, newcost, 0});
                }
            }
        }
    }
}

void precalc()
{
    for(int mask = 1; mask <= (1 << (k + 1)); mask ++)
    {
        int val = 0;
        for(int i = 1; i <= 16; i *= 2)
        {
            if(mask & i)
                val++;
        }
        cnt[mask] = val;
    }
}

int main()
{
    fin >> k >> n >> m;
    for(int i = 1; i <= k; i ++)
    {
        fin >> detinut[i];
    }
    while(m--)
    {
        int a, b, c, d;
        fin >> a >> b >> c >> d;
        v[a].push_back({b, c, d});
        v[b].push_back({a, c, d});
    }
    precalc();
    for(int i = 1; i <= k; i ++)
    {
        for(int j = 1; j <= k; j ++)
        {
            for(int q = 1; q <= n; q ++)
            {
                dp[i][j][q] = INT_MAX;
            }
        }
    }

    for(int i = 1; i <= k; i ++)
    {
        for(int j = 1; j <= k; j ++)
        {
            Dijkstra(i, j);
        }
    }
    for(int i = 1; i <= k; i ++)
    {
        for(int j = 1; j <= (1 << (k + 1)); j ++)
        {
            dist[i][j] = INT_MAX;
        }
    }
    for(int i = 1; i <= k; i ++)
    {
        dist[i][(1 << i)] = dp[i][1][1];
    }
    for(int mask = 1; mask <= (1 << (k + 1)); mask ++)
    {
        for(int i = 1; i <= k; i ++)
        {
            if(mask & (1 << i))
            {
                for(int j = 1; j <= k; j ++)
                {
                    int val = mask & (1 << j);
                    if(val == 0)
                    {
                        if(dp[i][cnt[mask]][detinut[j]] != INT_MAX)
                            dist[j][mask + (1 << j)] = min(dist[j][mask + (1 << j)], dist[i][mask] + (cnt[mask] + 1) * dp[i][cnt[mask]][detinut[j]]);
                    }
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i = 1; i <= k; i ++)
    {
        ans = min(ans, dist[i][(1 << (k + 1)) - 2]);
    }
    fout << ans << '\n';
    return 0;
}