#pragma GCC optimize("O3")
#include <cstdio>
#include <queue>
#include <random>
#include <algorithm>
using namespace std;
int main(){
int n, k, m;
scanf("%d%d%d", &n, &k, &m);
vector <vector <int> > adjLis1(n);
vector <vector <long long> > disLis1(n);
vector <int> important(k);
for(int& i:important){
scanf("%d", &i);
i--;
}
while(k<4){
important.push_back(important.back());
k++;
}
for(int i = m;i --;){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a--;b--;
adjLis1[a].push_back(b);
disLis1[a].push_back(c);
adjLis1[b].push_back(a);
disLis1[b].push_back(c);
}
vector <vector <long long> > multisource(k, vector <long long> (n, 1e14));
for(int i = 0;i < k;i ++){
vector <long long>& dist=multisource[i];
int source=important[i];
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
for(int i = 0;i < adjLis1[x].size();i ++){
int y=adjLis1[x][i];
long long dd=disLis1[x][i];
if(dist[y]>d+dd){
dist[y]=d+dd;
dijkstra.push(make_pair(dist[y], y));
}
}
}
}
if(k==5){
mt19937 rng(38752);
shuffle(important.begin(), important.end(), rng);
long long best=1e14;
vector <long long> dist;
for(int i = 0;i < 15;i ++){
//test here
//construct graph
/*
0..n-1 :layer 1
n..2n-1 :layer 2
2n :source
2n+1 :sink
max flow but not maxflow :v
*/
vector <vector <int> > adjLis2(n*2+2);
vector <vector <long long> > disLis2(n*2+2);
for(int i = 0;i < n;i ++){
for(int j = 0;j < adjLis1[i].size();j ++){
//layer1
adjLis2[i].push_back(adjLis1[i][j]);
disLis2[i].push_back(disLis1[i][j]);
//layer2
adjLis2[i+n].push_back(adjLis1[i][j]+n);
disLis2[i+n].push_back(disLis1[i][j]);
if(clock()>3.99*CLOCKS_PER_SEC){
printf("%lld\n", best);
return 0;
}
}
//sink --> layer1
adjLis2[2*n].push_back(i);
disLis2[2*n].push_back(multisource[1][i]+multisource[2][i]);
//layer1 --> layer2
adjLis2[i].push_back(i+n);
disLis2[i].push_back(multisource[0][i]);
//layer2 --> sink
adjLis2[i+n].push_back(2*n+1);
disLis2[i+n].push_back(multisource[3][i]+multisource[4][i]);
if(clock()>3.99*CLOCKS_PER_SEC){
printf("%lld\n", best);
return 0;
}
}
//dijkstra again
dist.assign(n*2+2, 1e14);
int source=n*2, sink=n*2+1;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
if(x==sink)
break;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=disLis2[x][i];
if(dist[y]>d+dd){
dist[y]=d+dd;
dijkstra.push(make_pair(dist[y], y));
}
if(clock()>3.99*CLOCKS_PER_SEC){
printf("%lld\n", best);
return 0;
}
}
}
best=min(best, dist[sink]);
//switching here
if(i%3==0){
// swap(important[2], important[3]);
swap(multisource[2], multisource[3]);
}else if(i%3==1){
// swap(important[2], important[4]);
swap(multisource[2], multisource[4]);
}else if(i%3==2){
if(i==2){
// swap(important[0], important[1]);
swap(multisource[0], multisource[1]);
}else if(i==5){
// swap(important[0], important[4]);
swap(multisource[0], multisource[4]);
}else if(i==8){
// swap(important[0], important[3]);
swap(multisource[0], multisource[3]);
}else if(i==11){
// swap(important[0], important[2]);
swap(multisource[0], multisource[2]);
}else{
// :)
}
}
}
printf("%lld\n", best);
}else{
long long best=1e14;
vector <long long> dist;
for(int i = 0;i < 3;i ++){
//test here
//construct graph
/*
0..n-1 :layer 1
n :source
n+1 :sink
max flow but not maxflow :v
*/
vector <vector <int> > adjLis2(n+2);
vector <vector <long long> > disLis2(n+2);
for(int i = 0;i < n;i ++){
for(int j = 0;j < adjLis1[i].size();j ++){
//layer1
adjLis2[i].push_back(adjLis1[i][j]);
disLis2[i].push_back(disLis1[i][j]);
}
//sink --> layer1
adjLis2[n].push_back(i);
disLis2[n].push_back(multisource[0][i]+multisource[1][i]);
//layer1 --> sink
adjLis2[i].push_back(n+1);
disLis2[i].push_back(multisource[2][i]+multisource[3][i]);
}
//dijkstra again
dist.assign(n+2, 1e14);
int source=n, sink=n+1;
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
dist[source]=0ll;
dijkstra.push(make_pair(dist[source], source));
while(!dijkstra.empty()){
int x=dijkstra.top().second;
long long d=dijkstra.top().first;
dijkstra.pop();
if(dist[x]!=d)
continue;
if(x==sink)
break;
for(int i = 0;i < adjLis2[x].size();i ++){
int y=adjLis2[x][i];
long long dd=disLis2[x][i];
if(dist[y]>d+dd){
dist[y]=d+dd;
dijkstra.push(make_pair(dist[y], y));
}
}
}
best=min(best, dist[sink]);
//switching here
if(i%3==0){
swap(multisource[1], multisource[2]);
}else if(i%3==1){
swap(multisource[1], multisource[3]);
}else if(i%3==2){
// :)
}
}
printf("%lld\n", best);
}
}
