#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
#define ll long long
#define INF 1e17
#define X first
#define Y second
int key[5];
ll dist[5][100005];
ll dist2[5][5][100005];
int perm[5];
bool status[5];
vector<pair<int, int>> stage[100005];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq2;
void dijkstra(int idx, int st)
{
dist[idx][st] = 0;
pq.push({0, st});
while(!pq.empty())
{
ll d; int cur;
tie(d, cur) = pq.top(); pq.pop();
if(dist[idx][cur] != d)
continue;
for(auto& nxt : stage[cur])
if(dist[idx][nxt.X] > d + nxt.Y)
{
dist[idx][nxt.X] = d + nxt.Y;
pq.push({dist[idx][nxt.X], nxt.X});
}
}
}
void dijkstra2(int k, int n)
{
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
for(int x = 1; x <= n; x++)
{
dist2[i][j][x] = dist[i][x] + dist[j][x];
pq2.push({dist2[i][j][x], i, j, x});
}
while(!pq2.empty())
{
ll d; int u, v, x;
tie(d, u, v, x) = pq2.top(); pq2.pop();
if(dist2[u][v][x] != d)
continue;
for(auto& nxt : stage[x])
if(dist2[u][v][nxt.X] > d + nxt.Y)
{
dist2[u][v][nxt.X] = d + nxt.Y;
pq2.push({dist2[u][v][nxt.X], u, v, nxt.X});
}
}
}
ll solve(int k, int n)
{
ll ret = INF;
if(k == 2)
for(int i = 1; i <= n; i++)
ret = min(ret, dist[perm[0]][i] + dist[perm[1]][i]);
else if(k == 3)
for(int i = 1; i <= n; i++)
ret = min(ret, dist2[perm[0]][perm[1]][i] + dist[perm[2]][i]);
else if(k == 4)
for(int i = 1; i <= n; i++)
ret = min(ret, dist2[perm[0]][perm[1]][i] + dist2[perm[2]][perm[3]][i]);
else
for(int i = 1; i <= n; i++)
ret = min(ret, dist2[perm[0]][perm[1]][i] + dist2[perm[2]][perm[3]][i] + dist[perm[4]][i]);
return ret;
}
void permutate(int p, int k, int n, ll& ans)
{
if(p == k)
ans = min(ans, solve(k, n));
else
{
for(int i = 0; i < k; i++)
if(!status[i])
{
status[i] = 1;
perm[p] = i;
permutate(p+1, k, n, ans);
status[i] = 0;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, m;
cin >> n >> k >> m;
for(int i = 0; i < k; i++)
cin >> key[i];
while(m--)
{
int u, v, c;
cin >> u >> v >> c;
stage[u].push_back({v, c});
stage[v].push_back({u, c});
}
for(int i = 0; i < k; i++)
{
fill(dist[i], dist[i]+n+1, INF);
dijkstra(i, key[i]);
}
dijkstra2(k, n);
ll ans = INF;
permutate(0, k, n, ans);
cout << ans << '\n';
}
