# include <cstdio>
# include <cstring>
# include <queue>
# include <vector>
using namespace std;
const char *FIN = "team.in", *FOU = "team.out";
const int MAX_N = 505, MAX_P = 55, oo = 0x3f3f3f3f, hg = 1 << 13;
# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0
# define x first
# define y second
bool viz[MAX_N];
int N, M, P, dp[MAX_N], dist[MAX_P][MAX_P], d[MAX_P], sol[MAX_P][MAX_P][MAX_P], poz;
char ch[hg];
vector < pair <int, int> > G[MAX_N];
struct comp {
bool operator () (const int &A, const int &B) {
return dp[A] > dp[B];
}
};
priority_queue < int, vector <int>, comp > Q ;
inline void getmin (int &a, int b) {
a = a < b ? a : b;
}
inline bool cit ( int &x ) {
if ( ch[0] == '\0' ) fread ( ch, 1, hg, stdin ) ;
else for ( ; ch[poz] < '0' || ch[poz] > '9' ; verf ) ;
for ( x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' ; x = x * 10 + ch[poz] - '0', verf ) ;
return 1;
}
void dijkstra (int nod) {
memset (dp, oo, sizeof (dp)), memset (viz, 0, sizeof (viz));
for (dp[nod] = 0, viz[nod] = 1, Q.push (nod); ! Q.empty (); ) {
int act = Q.top (); viz[act] = 0; Q.pop ();
for (vector < pair <int, int> > :: iterator it = G[act].begin (); it != G[act].end (); ++it)
if (dp[act] + it -> second < dp[it -> first]) {
dp[it -> first] = dp[act] + it -> second;
if (viz[it -> first] == 0) {
Q.push (it -> first);
viz[it -> first] = 1;
}
}
}
}
int din (int x, int y, int z) {
if (sol[x][y][z] != oo) return sol[x][y][z];
if (x > y) return 0;
for (int i = x; i <= y; ++i)
getmin (sol[x][y][z], din (x, i - 1, i) + din (i + 1, y, i) + dist[z][i]);
return sol[x][y][z];
}
int main (void) {
freopen (FIN, "r", stdin);
cit (P), cit (N), cit (M);
for (int i = 1, x, y, z; i <= M; ++i) {
cit (x), cit (y), cit (z);
G[x].push_back (make_pair (y, z));
G[y].push_back (make_pair (x, z));
}
for (int i = 0; i <= P; ++i)
i ? cit (d[i]) : d[i] = 1;
for (int i = 0; i <= P; ++i) {
dijkstra (d[i]);
for (int j = 0; j <= P; ++j)
dist[i][j] = dp[d[j]];
}
memset (sol, oo, sizeof (sol));
fprintf (fopen (FOU, "w"), "%d", din (1, P, 0));
}