#include<fstream>
#include<vector>
#include<limits>
#include<queue>
using namespace std;
ifstream fin("gather.in");
ofstream fout("gather.out");
const int INF = numeric_limits<int>::max();
int P[16];
long long Dist[16][16][755], Dp[16][(1<<15)], sol;
int k, n, m;
struct edge{
    int vec, L, C;
    edge( int to, int len, int cap ){
        this->vec = to;
        this->L = len;
        this->C = cap;
    }
};
inline edge make_edge( int to, int len, int cap ){
    edge aux( to, len, cap );
    return aux;
}
vector<edge> v[755];
priority_queue< pair<long long,int>, vector< pair<long long,int> >, greater< pair<long long,int> > > q;
void DK( int S, int Cmin ){
    Dist[S][Cmin][ P[S] ] = 0;
    q.push( make_pair( 0, P[S] ) );
    while( !q.empty() ){
        pair<long long,int> nod = q.top();
        q.pop();
        if( nod.first != Dist[S][Cmin][ nod.second ] )
            continue;
        for( int i = 0; i < v[nod.second].size(); i++ ){
            edge curr = v[nod.second][i];
            if( Dist[S][Cmin][curr.vec] > Dist[S][Cmin][nod.second] + curr.L && curr.C >= Cmin ){
                Dist[S][Cmin][curr.vec] = Dist[S][Cmin][nod.second] + curr.L;
                q.push( make_pair( Dist[S][Cmin][curr.vec], curr.vec ) );
            }
        }
    }
    return;
}
int main(){
    fin >> k >> n >> m;
    for( int i = 0; i < k; i++ )
        fin >> P[i];
    P[k] = 1;
    for( int i = 1; i <= m; i++ ){
        int a, b, c, d;
        fin >> a >> b >> c >> d;
        v[a].push_back( make_edge( b, c, d ) );
        v[b].push_back( make_edge( a, c, d ) );
    }
    for( int s = 0; s <= k; s++ )
        for( int cap = 0; cap <= k; cap++ )
            for( int i = 1; i <= n; i++ )
                Dist[s][cap][i] = INF;
    DK( k, 0 );
    for( int s = 0; s <= k; s++ ){
        for( int cap = 1; cap <= k; cap++ ){
            DK( s, cap );
        }
    }
    for( int conf = 0; conf < (1<<k); conf++ )
        for( int i = 0; i <= k; i++ )
            Dp[i][conf] = INF;
    Dp[k][0] = 0;
    for( int conf = 0; conf < (1<<k); conf++ ){
        int nrp = 0;
        for( int j = 0; j < k; j++ )
            if( ( (conf>>j) & 1 ) == 1 )
                nrp++;
        for( int i = 0; i <= k; i++ ){
            if( Dp[i][conf] != INF ){
                for( int j = 0; j < k; j++ ){
                    if( ( (conf>>j) & 1 ) == 0 && Dist[i][nrp][ P[j] ] != INF )
                        if( Dp[j][conf + (1<<j)] > Dp[i][conf] + (nrp + 1) * Dist[i][nrp][ P[j] ] )
                            Dp[j][conf + (1<<j)] = Dp[i][conf] + (nrp + 1) * Dist[i][nrp][ P[j] ];
                }
            }
        }
    }
    sol = INF;
    for( int j = 0; j <= k; j++ )
        sol = min( sol, Dp[j][ (1<<k) - 1 ] );
    fout << sol << "\n";
    return 0;
}