#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <fstream>
#include <queue>

using namespace std;

#define pb push_back
#define mp make_pair

#define maxN 504
#define maxP 53
#define inf 1000000000

struct state {
    int node;
    int lr;
    int cost;

    bool operator<(const state& who)const {
        return cost > who.cost;
    }
};

int p, n, m, i, j, k, x, y, c;
vector< pair<int, int> > list[maxN];
int dp[maxN][maxP][maxP];

priority_queue<state> H;
vector<int> who[maxN];
state act;
int node, l, r, cost;

void set_state(int node, int l, int r, int cost) {
    static state aux;

    if (dp[node][l][r] <= cost) return;
    dp[node][l][r] = cost;

    aux.node = node;
    aux.lr = l * 1000 + r;
    aux.cost = cost;

    H.push(aux);
}

int main()
{
    freopen("team.in", "r", stdin);
    freopen("team.out", "w", stdout);

    scanf("%d%d%d", &p, &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &c);
        list[x].pb(mp(y, c));
        list[y].pb(mp(x, c));
    }

    for (i = 1; i <= p; i++) {
        scanf("%d", &x);
        who[x].pb(i);
    }

    for (i = 1; i <= n; i++)
        for (j = 1; j <= p; j++)
            for (k = j; k <= p; k++)
                dp[i][j][k] = inf;

    for (i = 1; i <= n; i++) {
        for (j = 0; j < who[i].size(); j = k) {
            for (k = j + 1; k < who[i].size(); k++)
                if (who[i][k - 1] + 1 != who[i][k])
                    break;

            set_state(i, who[i][j], who[i][k - 1], 0);
        }
    }

    while (!H.empty()) {
        act = H.top(); H.pop();
        node = act.node;
        l = act.lr / 1000;
        r = act.lr % 1000;
        cost = act.cost;

        if (node == 1 && l == 1 && r == p) {
            printf("%d", cost);
            cerr << cost;
            exit(0);
        }

        if (dp[node][l][r] != cost) continue;

        for (i = 1; i < l; i++)
            set_state(node, i, r, cost + dp[node][i][l - 1]);
        for (i = r + 1; i <= p; i++)
            set_state(node, l, i, cost + dp[node][r + 1][i]);
        for (i = 0; i < list[node].size(); i++) {
            int to = list[node][i].first;
            int cc = list[node][i].second;

            set_state(to, l, r, cost + cc);
        }
    }


    return 0;
}