#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
#include <string>
#include <stack>
#include <deque>
#include <iomanip>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
#include <list>
#include <iomanip>

using namespace std;

string file = "gather";

ifstream cin( (file + ".in").c_str() );
ofstream cout( (file + ".out").c_str() );

const int MAXN = 755;
const int MAXK = 16;
const int oo = 0x3f3f3f3f;

class trio {
    public:
    int x, y, z;
    trio(int x, int y, int z) {
        this->x = x;
        this->y = y;
        this->z = z;
    }
};

typedef vector<trio> Graph[MAXN];
typedef vector<trio> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int K, N, M, det[MAXK], dp[MAXK][MAXK][MAXN], a[1 << MAXK][MAXK];
Graph G;
priority_queue<pair<int,int> , vector<pair<int, int> > , greater<pair<int, int> > > Q;

inline void Dijkstra(int i, int j, int best[]) {
    best[i] = 0;
    Q.push(make_pair(best[i], i));
    for( ; !Q.empty() ; ) {
        int Node = Q.top().second;
        Q.pop();
        for(It it = G[Node].begin(), fin = G[Node].end(); it != fin ; ++ it)
            if(best[it->x] > best[Node] + it->y && it->z >= j) {
                best[it->x] = best[Node] + it->y;
                Q.push(make_pair(best[it->x], it->x));
            }
    }
}

inline int bits(int conf) {
    int ret = 0;
    while(conf) {
        conf &= (conf-1);
        ++ ret;
    }
    return ret;
}

int main() {
    cin >> K >> N >> M;
    ++ K;
    for(int i = 1 ; i < K ; ++ i) {
        cin >> det[i];
        -- det[i];
    }
    for(int i = 1 ; i <= M ; ++ i) {
        int x, y, z, d;
        cin >> x >> y >> z >> d;
        -- x;
        -- y;
        G[x].push_back(trio(y, z, d));
        G[y].push_back(trio(x, z, d));
    }
    /// dp[i][j][k] =  min i -> k , cap <= j
    /// a[conf][i] =
    memset(dp, oo, sizeof(dp));
    for(int i = 0 ; i <= K ; ++ i)
        for(int j = 0 ; j <= K ; ++ j)
            Dijkstra(det[i], j, dp[i][j]);
    memset(a, oo, sizeof(a));
    a[1][0] = 0;
    int maxconf = (1 << K);
    for(int conf = 2 ; conf < maxconf ; ++ conf) {
        int nrconf = bits(conf);
        -- nrconf;
        for(int i = 0 ; i < K ; ++ i)
            if(conf & ( 1 << i )) {/// i e in conf
                for(int j = 0 ; j < K ; ++ j) { /// vin din nodulul dis[j]
                    int actConf = conf ^ ( 1 << i );
                    if(a[actConf][j] == oo || dp[j][nrconf][det[i]] == oo)
                        continue;
                    a[conf][i] = min(a[conf][i], a[actConf][j] + nrconf * dp[j][nrconf-1][det[i]]);
                }
            }
    }
    int Ans = oo;
    for(int i = 0 ; i < K ;++ i)
        Get_min(Ans, a[maxconf-1][i]);
    cout << Ans << '\n';
    cin.close();
    cout.close();
    return 0;
}