#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 2000, KMAX = 15, INF = 1e9;
struct edge {
int nd, cst;
};
struct cmp {
bool operator()(const edge& a, const edge& b) { // returnez 1 daca a are prioritatea strict mai mare decat b
return a.cst > b.cst;
}
};
int kadj[KMAX + 1][KMAX + 1];
int ind[NMAX], dsea[KMAX + 1];
bool isk[NMAX];
int kcity[KMAX + 1];
vector<edge> adj[NMAX];
priority_queue<edge, vector<edge>, cmp> heap;
int hamilton[1 << (KMAX + 1)][KMAX + 1], minDist[NMAX];
void dij(int start, int n);
int main()
{
int n, m, k, i, j, p, nd1, nd2, c;
FILE *fin = fopen("ubuntzei.in", "r");
fscanf(fin, "%d%d", &n, &m);
fscanf(fin, "%d", &k);
kcity[0] = 0, isk[0] = 1, ind[0] = 0;
dsea[0] = INF;
for (i = 1; i <= k; i++) {
dsea[i] = INF;
fscanf(fin, "%d", &kcity[i]);
kcity[i]--;
ind[kcity[i]] = i;
isk[kcity[i]] = 1;
}
for (i = 0; i < m; i++) {
fscanf(fin, "%d%d%d", &nd1, &nd2, &c);
nd1--, nd2--;
adj[nd1].push_back({nd2, c});
adj[nd2].push_back({nd1, c});
}
fclose(fin);
for (i = 0; i <= k; i++)
for (j = 0; j <= k; j++)
kadj[i][j] = INF;
for (i = 0; i <= k; i++)
dij(kcity[i], n);
for (i = 1; i <= (1 << (k + 1)); i++)
for (j = 0; j <= k; j++)
hamilton[i][j] = INF;
hamilton[1][0] = 0;
for (i = 1; i < (1 << (k + 1)); i += 2)
for (j = 0; j <= k; j++) {
if (((i >> j) & 1) == 0)
continue;
for (p = 0; p <= k; p++) {
if (p == j || ((i >> p) & 1) == 0)
continue;
int lst = i ^ (1 << j);
hamilton[i][j] = min(hamilton[i][j], hamilton[lst][p] + kadj[p][j]);
}
}
int minn = INF, cm = (1 << (k + 1)) - 1;
for (i = 0; i <= k; i++)
minn = min(minn, hamilton[cm][i] + dsea[i]);
FILE *fout = fopen("ubuntzei.out", "w");
fprintf(fout, "%d", minn);
fclose(fout);
return 0;
}
void dij(int start, int n) {
for (int i = 0; i < n; i++)
minDist[i] = INF;
minDist[start] = 0;
heap = priority_queue<edge, vector<edge>, cmp>();
heap.push({start, 0});
while (!heap.empty()) {
edge e = heap.top();
heap.pop();
if (e.cst == minDist[e.nd]) {
if (isk[e.nd])
kadj[ind[start]][ind[e.nd]] = e.cst;
if (e.nd == n - 1)
dsea[ind[start]] = e.cst;
for (vector<edge>::iterator nxt = adj[e.nd].begin(); nxt != adj[e.nd].end(); nxt++) {
if (nxt -> cst + e.cst < minDist[nxt -> nd]) {
minDist[nxt -> nd] = nxt -> cst + e.cst;
heap.push({nxt -> nd, minDist[nxt -> nd]});
}
}
}
}
}