#include <bits/stdc++.h>

using namespace std;

/// 21:50

class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

ofstream fout("gather.out");

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

int k, n, m;
int detinut[KMAX + 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;
};

vector<elem> v[NMAX + 5];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> coada;


void Dijkstra(int start, int minim)
{
    coada.push({0, detinut[start]});
    dp[start][minim][detinut[start]] = 0;
    while(!coada.empty())
    {
        int nod = coada.top().second;
        int cost = coada.top().first;
        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({newcost, it.nod});
                }
            }
        }
    }
}

int main()
{
    InParser fin("gather.in");
    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});
    }
    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)
                    {
                        dist[j][mask + (1 << j)] = min(dist[j][mask + (1 << j)], dist[i][mask] + (__builtin_popcount(mask) + 1) * dp[i][__builtin_popcount(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;
}