#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

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

const int MAX_N = 750;
const int MAX_K = 15;
const int INF = 0x3fffffff;

struct nodeDist {
    int node;
    int dist;
};

struct Edge {
    int v;
    int c;
    int d;
};

class pqCompare1 {
public:
    bool operator ()(nodeDist A, nodeDist B) {
      return A.dist > B.dist;
    }
};

int n, k, m;
int iP[1 + MAX_N];
int P[1 + MAX_K];
int D[1 + MAX_K][1 + MAX_K][1 + MAX_K];
int Dist[1 + MAX_N];
vector < Edge > A[1 + MAX_N];
priority_queue < nodeDist, vector < nodeDist >, pqCompare1 > Q;

void initDijkstra(int s) {
    memset(Dist, 0, sizeof(Dist));
    while(!Q.empty()) Q.pop();

    for(int i = 1; i <= n; i++) Dist[i] = INF;
    Dist[s] = 0;
    Q.push({s, 0});
}

void dijkstra(int s, int minD) {
    int i, u, v, du, c;

    initDijkstra(s);
    while(!Q.empty()) {
        u = Q.top().node;
        du = Q.top().dist;
        Q.pop();

        if(Dist[u] != du) continue;
        for(i = 0; i < A[u].size(); i++) {
            v = A[u][i].v;
            c = A[u][i].c;
            if(A[u][i].d >= minD) {
                if(du + c < Dist[v]) {
                    Dist[v] = du + c;
                    Q.push({v, Dist[v]});
                }
            }
        }
    }

    out << s << " " << minD << "\n";
    for(i = 1; i <= n; i++) out << Dist[i] << " ";
    out << "\n\n";
}

void getPairDistances() {
    int i, j, t;

    for(i = 1; i <= k; i++) {
        for(t = 1; t <= k; t++) {
            dijkstra(P[i], t);
            for(j = 1; j <= k; j++) {
                D[i][j][t] = Dist[P[j]];
            }
        }
    }
}

struct nodeCfg {
    int node;
    int cfg;
    int nBits;
    int dist;
};

int getEdge(nodeCfg A, nodeCfg B) {
    return D[A.node][B.node][A.nBits];
}

class pqCompare2 {
public:
    bool operator ()(nodeCfg A, nodeCfg B) {
        return A.dist > B.dist;
    }
};

int dFinal[1 + MAX_K][1 << MAX_K];
priority_queue < nodeCfg, vector < nodeCfg >, pqCompare2 > Q2;

void initDijkstra2() {
    int i, j;
    for(i = 1; i <= k; i++) {
        for(j = 0; j < (1 << MAX_K); j++) {
            dFinal[i][j] = INF;
        }
    }
    dFinal[1][0] = 0;
    Q2.push({1, 0, 1, 0});
}

void Dijkstra2() {
    int i, j, c;
    nodeCfg U, V;

    initDijkstra2();
    while(!Q2.empty()) {
        U = Q2.top();
        Q2.pop();

        if(U.dist != dFinal[U.node][U.cfg]) continue;
        for(i = 1; i <= k; i++) {
            if((U.cfg & (1 << (i-1))) == 0) {
                V.node = i;
                V.cfg = U.cfg + (1 << (i-1));
                V.nBits = U.nBits + 1;

                c = getEdge(U, V);
                out << U.node << " " << U.cfg << " | " << V.node << " " << V.cfg << " -- " << c << "\n";
                if(dFinal[U.node][U.cfg] + c < dFinal[V.node][V.cfg]) {
                    dFinal[V.node][V.cfg] = dFinal[U.node][U.cfg] + c;
                    V.dist = dFinal[V.node][V.cfg];
                    Q2.push(V);
                }
            }
        }

    }
}

void solve() {
    int i, dMin = INF;
    for(i = 1; i <= k; i++) {
        dMin = min(dMin, dFinal[i][(1 << k) -1]);
    }
    out << dMin << "\n";

    int j;
    for(i = 1; i <= k; i++) {
        for(j = 0; j <= (1 << k) - 1; j++) {
            out << dFinal[i][j] << " ";
        }
        out << "\n";
    }
}

int main() {
    int i, j, u, v, c, d;

    in >> k >> n >> m;
    for(i = 1, j = 1; i <= k; i++) {
        in >> u;
        P[j] = u;
        iP[u] = j;
        j++;
    }

    for(i = 1; i <= m; i++) {
        in >> u >> v >> c >> d;
        A[u].push_back({v, c, d});
        A[v].push_back({u, c, d});
    }

    for(i = 0; i <= MAX_K; i++) {
        for(j = 0; j <= MAX_K; j++) {
            for(u = 0; u <= MAX_K; u++) {
                D[i][j][u] = INF;
            }
        }
    }

    Dijkstra(1, )
    getPairDistances();


    int t;
    for(i = 1; i <= k; i++) {
        for(j = 1; j <= k; j++) {
            for(t = 1; t <= k; t++) {
                out << i << " " << j << " " << t << " " << D[i][j][t] << "\n";
            }
        }
    }
    Dijkstra2();
    solve();

    return 0;
}